Opis wyzwania

Dla każdej dodatniej liczby całkowitej nistnieje liczba, której postać 111...10...000jest podzielna przez nnp. Liczbę dziesiętną, która zaczyna się od wszystkich 1, a kończy na wszystkich 0. Jest to bardzo łatwe do udowodnienia: jeśli weźmiemy zestaw n+1różnych liczb w postaci 111...111(wszystkich 1), to co najmniej dwie z nich podadzą tę samą resztę po podzieleniu przez n(zgodnie z zasadą szufladki). Różnica tych dwóch liczb będzie podzielna przez ni będzie miała pożądaną formę. Twoim celem jest napisanie programu, który znajdzie ten numer.

Opis wejściowy

Dodatnia liczba całkowita.

Opis wyników

Liczba pw postaci 111...10...000takiej, że p ≡ 0 (mod n). Jeśli znajdziesz więcej niż jeden - wyświetl dowolny z nich (nie musi być najmniejszy).

Uwagi

Twój program musi udzielić odpowiedzi w rozsądnym czasie. Co oznacza, że ​​brutalne wymuszanie jest niedozwolone:

p = 0
while (p != 11..10.00 and p % n != 0)
    p++

To też nie jest:

do
    p = random_int()
while (p != 11..10.00 and p % n != 0)

Iterowanie po liczbach w postaci 11..10..00jest dozwolone.

Twój program nie musi obsługiwać dowolnie dużych danych wejściowych - górna granica jest równa górnej granicy twojego języka.

Przykładowe wyniki

2: 10
3: 1110
12: 11100
49: 1111111111111111111111111111111111111111110
102: 1111111111111111111111111111111111111111111111110

Mathematica, 29 bajtów

⌊10^(9EulerPhi@#)/9⌋10^#&

Kod autorstwa Martina Büttnera .

Na wejściu n, to wyświetla liczbę z 9*ϕ(n)nich następnie nzer, gdzie ϕpada funkcja totient Eulera . Za pomocą funkcji phimożna to wyrazić w Pythonie jako

lambda n:'1'*9*phi(n)+'0'*n

Wystarczy użyć silni n!zamiast ϕ(n), ale drukowanie wielu nie ma rozsądnego czasu działania.

Twierdzenie: zera 9*ϕ(n)po nzerach to wielokrotność n.

Dowód: Najpierw udowodnić to na wypadek, że nnie jest wielokrotnością 2, 3lub 5. Pokażemy, że liczba składająca się z ϕ(n)nich jest wielokrotnością `n.

Ich liczba kjest równa (10^k-1)/9. Ponieważ nnie jest wielokrotnością 3, jest to wielokrotność ntak długa, jak 10^k-1współczynnik nlub równoważnie jeśli 10^k = 1 (mod n). Zauważ, że to sformułowanie pokazuje, że jeśli kdziała dla wielu, to robi to dowolna wielokrotność k.

Więc szukamy kbyć wielokrotnością kolejności od kw multiplikatywnego grupa modulo n . Zgodnie z twierdzeniem Lagrange'a każda taka kolejność jest dzielnikiem wielkości grupy. Ponieważ elementami grupy są liczby od 1do, nktóre są względnie pierwsze do n, jej rozmiar jest funkcją sumaryczną Eulera ϕ(n) . Tak więc pokazaliśmy to 10^ϕ(n) = 1 (mod n), a więc ich liczba ϕ(n)jest wielokrotnością `n.

Teraz zajmiemy się potencjalnymi czynnikami 3w n. Wiemy, że 10^ϕ(n)-1jest to wielokrotność n, ale (10^ϕ(n)-1)/9może nie być. Ale (10^(9*ϕ(n))-1)/9jest wielokrotnością, 9ponieważ składa się z 9*ϕ(n)nich, więc suma jego cyfr jest wielokrotnością 9. Zauważyliśmy, że pomnożenie wykładnika kprzez stałą zachowuje podzielność.

Teraz, jeśli nma czynniki 2's i 5', musimy dodać zera na końcu wyniku. Jest to o wiele więcej niż wystarczające do używania nzer (w rzeczywistości log_2(n)by to zrobił). Tak więc, jeśli nasze dane wejściowe nsą podzielone jako n = 2^a * 5^b * m, wystarczy 9*ϕ(m), aby były one wielokrotnością n, pomnożone przez 10^nwielokrotność 2^a * 5^b. A ponieważ njest to wielokrotność m, wystarczy użyć 9*ϕ(n)tych. Więc działa tak, aby po 9*ϕ(n)nich były nzera.

Python 2, 44 bajty

f=lambda n,j=1:j/9*j*(j/9*j%n<1)or f(n,j*10)

Gdy jjest potęga 10, taka jak 1000, podział na piętra j/9daje liczbę złożoną z 1, takich jak 111. Zatem j/9*jdaje 1, a następnie równą liczbę zer, takich jak 111000.

Funkcja rekurencyjnie testuje liczby w tej formie, próbując coraz wyższych potęg 10, dopóki nie znajdziemy takiej, która jest wielokrotnością żądanej liczby.

Pyth, 11 bajtów

.W%HQsjZ`TT

Zestaw testowy

Zasadniczo po prostu umieszcza 1 z przodu i 0 z powrotem w kółko, aż liczba będzie podzielna przez dane wejściowe.

Wyjaśnienie:

.W%HQsjZ`TT
                Implicit: Q = eval(input()), T = 10
.W              while loop:
  %HQ           while the current value mod Q is not zero
      jZ`T      Join the string "10" with the current value as the separator.
     s          Convert that to an integer.
          T     Starting value 10.

Haskell, 51 bajtów

\k->[b|a<-[1..],b<-[div(10^a)9*10^a],b`mod`k<1]!!0

Korzystanie z podejścia xnor. nimi uratował bajt!

CJam, 28 25 19 bajtów

Zaoszczędziłem 6 bajtów z obserwacją xnora, że ​​wystarczy spojrzeć na liczby w formularzu .1n0n

ri:X,:)Asfe*{iX%!}=

Sprawdź to tutaj.

Wyjaśnienie

ri:X    e# Read input, convert to integer, store in X.
,:)     e# Get range [1 ... X].
As      e# Push "10". 
fe*     e# For each N in the range, repeat the characters in "10" that many times,
        e# so we get ["10" "1100" "111000" ...].
{iX%!}= e# Select the first element from the list which is divided by X.

Mathematica, 140 55 bajtów

NestWhile["1"<>#<>"0"&,"1",FromDigits@#~Mod~x>0&/.x->#]

Usunięto wiele bajtów dzięki sztuczce xnor 1 ^ n0 ^ n.

Minimalna wartość, 140 156 bajtów To daje najmniejsze możliwe rozwiązanie.

NestWhile["1"<>#&,ToString[10^(Length@NestWhileList[If[EvenQ@#,If[10~Mod~#>0,#/2,#/10],#/5]&,#,Divisors@#~ContainsAny~{2, 5}&],FromDigits@#~Mod~m>0&/.m->#]&

Oblicza, ile zer jest wymaganych, a następnie sprawdza wszystkie możliwe 1liczby, aż zadziała. Może wypisać liczbę bez 0, ale można to naprawić, dodając <>"0"prawo przed końcem &.

Haskell, 37 bajtów

f n=[d|d<-"10",i<-[1..n*9],gcd n i<2]

Wykorzystuje to fakt , że działa tak, aby mieć 9*phi(n)takie, gdzie phijest funkcja sumująca Eulera. Tutaj jest implementowany za pomocą gcdi filtrowania, generując jedną cyfrę dla każdej wartości, iktóra jest względnie pierwotna w zakresie 1i 9*n. Wystarczy również użyć tak wielu zer.

JavaScript (ES6), 65 bajtów

Edytuj 2 bajty zapisane thx @ Neil

Działa w granicach typu liczbowego javascript, z 17 cyframi znaczącymi. (Tak dość ograniczony)

a=>{for(n='';!(m=n+=1)[17];)for(;!(m+=0)[17];)if(!(m%a))return+m}  

Mniej golfa

function (a) {
    for (n = ''; !(m = n += '1')[17]; )
        for (; !(m += '0')[17]; )
            if (!(m % a))
                 return +m;
}

Perl 5, 26 bajtów

zawiera bajt dla -n( -M5.01jest bezpłatny)

($.="1$.0")%$_?redo:say$.

Sage, 33 bajty

lambda n:'1'*9*euler_phi(n)+'0'*n

Używa metody xnor do generowania danych wyjściowych.

Wypróbuj online

bc, 58 bajtów

define f(n){for(x=1;m=10^x/9*10^x;++x)if(m%n==0)return m;}

Przykładowe wyniki

200: 111000
201: 111111111111111111111111111111111000000000000000000000000000000000
202: 11110000
203: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000
204: 111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000
205: 1111100000
206: 11111111111111111111111111111111110000000000000000000000000000000000
207: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
208: 111111000000
209: 111111111111111111000000000000000000
210: 111111000000
211: 111111111111111111111111111111000000000000000000000000000000
212: 11111111111110000000000000
213: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
214: 1111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000
215: 111111111111111111111000000000000000000000
216: 111111111111111111111111111000000000000000000000000000
217: 111111111111111111111111111111000000000000000000000000000000
218: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
219: 111111111111111111111111000000000000000000000000

dc, 27 bajtów

Odsm[O*lmdO*sm+O*dln%0<f]sf

Definiuje funkcję, fktóra oczekuje argumentu w zmiennej n. Aby użyć go jako programu, ?sn lfx pdo odczytu ze standardowego wejścia, wywołaj funkcję i wydrukuj wynik na standardowe wyjście. Zmienna mi górna część stosu muszą zostać zresetowane do 10 (powtarzając Odsm), zanim fbędzie można ich ponownie użyć.

Wyniki:

200: 111000
201: 111111111111111111111111111111111000000000000000000000000000000000
202: 11110000
203: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000
204: 111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000
205: 1111100000
206: 11111111111111111111111111111111110000000000000000000000000000000000
207: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
208: 111111000000
209: 111111111111111111000000000000000000
210: 111111000000
211: 111111111111111111111111111111000000000000000000000000000000
212: 11111111111110000000000000
213: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
214: 1111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000
215: 111111111111111111111000000000000000000000
216: 111111111111111111111111111000000000000000000000000000
217: 111111111111111111111111111111000000000000000000000000000000
218: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
219: 111111111111111111111111000000000000000000000000