Tło

Ludzie rozmawiali o faktoryzacji na czacie, a my rozmawialiśmy o repunitach. Repunity to podzbiór liczb znanych jako repdigits, które są liczbami składającymi się tylko z powtarzających się cyfr, takich jak 222lub 4444444444444444, ale repunity składają się tylko z 1.

Pierwsze kilka repunits są zatem 1, 11, 111, itd. Są one określane przez R _n , to R ₁ = 1, R ₂ = 11, etc., i generowane są przez wzór R(n) = (10^n - 1)/9z n > 0.

Pierwotne faktoryzacja tych ponownych numerów następuje po sekwencji A102380 w OEIS. Na przykład:

R ₁ = 1
R ₂ = 11
R ₃ = 111 = 3 * 37
R ₄ = 1111 = 11 * 101
R ₅ = 11111 = 41 * 271
R ₆ = 111111 = 3 * 7 * 11 * 13 * 37
R ₇ = 1111111 = 239 * 4649
...

Wyzwanie

Napisać program lub funkcji, które po podaniu Wejście całkowitą N z n >= 2pośrednictwem standardowego wejścia lub równoważne , wyjść lub zwraca nowe czynniki pierwsze dla R _n , w dowolnej dogodnej postaci. „Nowe czynniki pierwsze” oznaczają tutaj wszystko, xgdzie xjest liczbą pierwszą R _n , ale xnie jest liczbą pierwszą dla żadnego poprzedniego R _k , z 1 <= k < n(tzn. Jeśli piszemy czynniki pierwsze dla wszystkich R w sekwencji, nie widzieliśmy xprzed).

Przykłady

Input: 6
Output: 7, 13
(because 3, 11, and 37 are factors of a smaller R_k)

Input: 19
Output: 1111111111111111111
(because R_19 is prime, so no other factors)

Input: 24
Output: 99990001
(because 3, 7, 11, 13, 37, 73, 101, 137, 9901 are factors of a smaller R_k)

Input: 29
Output: 3191, 16763, 43037, 62003, 77843839397
(because no factors of R_29 are also factors of a smaller R_k)

Dodatki:

• Twój kod może zrobić wszystko lub nic, jeśli n < 2.
• Można założyć, „rozsądny” górną granicę nw celach testowych i wykonanie - kod nie będzie oczekiwać na wyjście do n = 10000000, na przykład, ale twój algorytm powinien działać w takim przypadku, jeśli dany nieograniczonej mocy obliczeniowej i czasu.
• Oto strona poświęcona faktoryzacji repunitów w celach informacyjnych.
• Nie przejrzałem matematyki, ale proponuję hipotezę, że każdy n ma wyraźny wynik dla tego algorytmu - to znaczy, że n nie istnieje tak, że R _n nie ma nowych czynników. Oferuję nagrodę w wysokości 250 punktów, jeśli ktoś udowodni lub potwierdzi to w swojej odpowiedzi. Thomas Kwa zaproponował elegancki dowód , a ja przyznałem nagrodę.

Pyth, 16 14 13 bajtów

-F_m{P/^Td9SQ

Jak mogę powiedzieć, 19 trwa wiecznie.

-F_m{P/^Td9SQ      Implicit: Q = input
           SQ      Inclusive range 1 to Q
                        Implicit lambda d:
    {P                  unique primes dividing
       ^Td              10**d
      /   9                  //9
   m               map lambda over the range
   m{P/^Td9SQ      Unique prime factors of all repunits up to the Qth
  _                Reverse the list
-F                 Reduce by set difference

Wypróbuj tutaj .

Dowód, że każda ponowna komisja ma nowy czynnik główny

Za pomocą twierdzenia Zsigmondy'ego dowód jest prosty. Z Wikipedii:

W teorii liczb twierdzenie Zsigmondy'ego, nazwane na cześć Karla Zsigmondy'ego, stwierdza, że ​​jeśli a> b> 0 są liczbami całkowitymi, to dla dowolnej liczby całkowitej n ≥ 1 , istnieje liczba pierwsza p (zwane prymitywne prime dzielnik), który dzieli ⁿ - b ⁿ i nie dzielą się ^k - b ^k dla dowolnej liczby całkowitej dodatniej k <n , z następującymi wyjątkami: [rzeczy, które nie stosują tutaj].

Rozważ czasy powtórzeń 9: to znaczy 10 ⁿ -1 . Według Twierdzenia Zsigmondy'ego o a = 10 , b = 1 , istnieje pewna liczba pierwsza p | 10 ⁿ -1, które nie dzieli żadnych 10 ^k -1 , k <n .

• Ponieważ p jest liczbą pierwszą, a 10 ⁿ -1 = 9 · R _n , musi on podzielić albo 9, albo R _n .

• p nie może podzielić 9 , ponieważ 9 = 10 ¹ -1 .

• Dlatego p dzieli R _n .

• P nie można podzielić każdą R _k , ponieważ nie dzieli 10 ^k -1 = 9 · R _k .

Dlatego p z twierdzenia Zsigmondy'ego jest nowym czynnikiem podstawowym dowolnego R _n , n ≥ 2 . ∎

Przykład powtarzającego się nowego czynnika podstawowego

Liczba pierwsza 487 jest wielokrotnością liczby pierwszej R ₄₈₆ :

Według twierdzenia Fermata-Eulera, 10 ^487-1 ≡ 1 (mod 487) . Kolejność 10 mod 487, czyli najmniejsza potęga 10, czyli 1 mod 487, musi więc być dzielnikiem 486. W rzeczywistości kolejność wynosi 486. Zdarza się również, że nie tylko 10 ⁴⁸⁶ ≡ 1 (mod 487) , jest to również 1 (mod 487 ² ) .

Zobacz tutaj, że kolejność 10 mod 487 wynosi 486; to znaczy, że nie mniej niż 10 ^tys -1 można podzielić przez 487. Oczywiście 487 nie dzieli 9, więc musi podzielić R ₄₈₆ .

CJam, 18 bajtów

{{)'1*imf}%W%:-_&}

Sprawdź to tutaj.

Począwszy od 19 (pierwsza liczba powtórzeń po 2) potrwa dość długo.

Wyjaśnienie

Jest to blok bez nazwy (odpowiednik funkcji CJam), który oczekuje numeru wejściowego nna stosie i pozostawia listę głównych czynników:

{      e# Map this block over [0 1 ... n-1]...
  )'1* e#   Increment and create a string of that many 1s.
  i    e#   Convert to integer.
  mf   e#   Get its prime factors.
}%
W%     e# Reverse the list.
:-     e# Fold set difference onto the list, removing from the first list the elements of
       e# all other lists.
_&     e# Remove duplicates. Unfortunately, this necessary. Thomas Kwa found that the 486th
       e# repunit contains 487^2 (where 487 is a novel prime factor).

Haskell 86 bajtów

import Data.Numbers.Primes
f n=[x|x<-primeFactors$div(10^n-1)9,notElem x$f=<<[1..n-1]]

Przykład użycia: f 8-> [73,137].

Dużo zajmuje dużo czasu i pamięci n.

Bezpośrednie wdrożenie definicji: wziąć wszystkich czynników xod Rnktórych nie pojawi się wcześniej ( f=<<[1..n-1]są wszystkie czynniki pierwsze R1 ... R(n-1)).

Mathematica 82 74 63 bajty

Z 11 bajtami zaoszczędzonymi dzięki alephalpha.

Complement@@Reverse@FactorInteger[(10^Range@#-1)/9][[;;,;;,1]]&

Czynniki pierwsze R70

(10 ^ 70-1) / 9 = 1111111111111111111111111111111111111111111111111111111111111111111111

FactorInteger[(10^70 - 1)/9]

{{11, 1}, {41, 1}, {71, 1}, {239, 1}, {271, 1}, {4649, 1}, {9091, 1}, {123551, 1}, { 909091, 1}, {4147571, 1}, {102598800232111471, 1}, {265212793249617641, 1}}

Nowe czynniki pierwsze R70

Complement@@Reverse@FactorInteger[(10^Range@#-1)/9][[;;,;;,1]]&[70]

{4147571, 265212793249617641}

MATL , 25 bajtów

Działa to dla danych wejściowych do 16:

10,i:^9/Y[t0)Yftb!w\~s1=)

Następująca wersja wykorzystuje 31 bajtów i działa do 18. Dla 19wymaga około 4 GB pamięci (nie udało się go uruchomić).

10,i:^9/Y[t0)5X2Y%Yfotb!w\~s1=)

Przykład

>> matl
 > 10,i:^1-,9/t0)5X2Y%Yfotb!w\~s1=)
 > 
> 6
7 13

Wyjaśnienie

Rozważ wprowadzenie konkretności 6. Najpierw 111111obliczane są główne dzielniki ; w tym przypadku wyniki są 3, 7, 11, 13, 37. Wtedy operacja modulo (podział reszta) oblicza się dla wszystkich kombinacji liczb 1, 11... 111111i obliczone dzielnikami. Wykorzystuje to ukrytą ekspansję MATL-a. Wynik jest w tym przypadku macierzą 6x 5, przy czym każda kolumna odpowiada jednemu z dzielników. Akceptowane dzielniki (kolumny) to te, dla których tylko 1wartość (a mianowicie ostatnia) daje zero pozostałej.

10,i:^9/Y[   % generate vector with `1`, `11`, ... depending on input number, say "n"
t0)          % pick the last element: `111...1` (n ones)
5X2Y%        % * convert to uint64, so that larger numbers can be handled
Yf           % prime factors                                             
o            % * convert to double precision, so that modulus can be done
t            % duplicate                                                 
b            % bubble up element in stack                                
!            % transpose                                                 
w            % swap elements in stack                                    
\            % modulus after division (element-wise, singleton expansion)
~s           % number of zero values in each column
1=           % is equal to 1? (element-wise, singleton expansion)
)            % index divisors with that logical index

(*) Usunięto w krótkiej wersji

Julia, 103 bajty

R(n)=[keys(factor((10^n-1)÷9))...]
n->(r=R(n);isprime(r)?r:setdiff(r,reduce(vcat,[R(i)for i=1:n-1])))

Jest to nienazwana funkcja, która wywołuje funkcję pomocnika R. Aby go wywołać, nadaj głównej funkcji nazwę, npf=n->... .

Nie golfowany:

function R(n::Integer)
    collect(keys(factor((10^n - 1) ÷ 9)))
end

function f(n::Integer)
    r = R(n)
    if isprime(r)
        r
    else
        setdiff(r, reduce(vcat, [R(i) for i = 1:n-1]))
    end
end

LabVIEW, 33 LabVIEW Prymitywy

19 trwa wiecznie ...

Pracuj, zapisując wszystkie liczby pierwsze i usuwając elementy z ostatniego zestawu, gdy zostaną znalezione w drugiej tablicy.

J, 24 bajty

[:({:-.}:)@:q:[:+/\10^i.

Oczekuje liczb o rozszerzonej precyzji po 6 (np. 19xZamiast 19).

Wypróbuj online!

Prawdopodobnie istnieje krótszy sposób generowania powtórek, który pozwala również uniknąć limitów.

Wyjaśnienie

[: ({: -. }:) @: q: [: +/\ 10 ^ i.
                                i. Range [0, input)
                           10 ^    10 raised to the power of the range
                       +/\         Running sum of this list (list of repunits)
                 q:                Prime factors of the repunits
              @:                   Composed with
   ({: -. }:)                      Unique prime factors of last repunit
    {:                              Factors of last repunit (tail of matrix)
       -.                           Set subtraction with
          }:                        Rest of the matrix (curtail)

Jak to działa wizualnie

Myślę, że tego rodzaju wizualne wyjaśnienia są łatwiejsze do zniesienia dla tych, którzy nie znają J. To są wyniki REPL.

   10 ^ i.6
1 10 100 1000 10000 100000

   +/\ 10 ^ i. 6
1 11 111 1111 11111 111111

   q: +/\ 10 ^ i. 6
 0   0  0  0  0
11   0  0  0  0
 3  37  0  0  0
11 101  0  0  0
41 271  0  0  0
 3   7 11 13 37

   ({: -. }:) q: +/\ 10 ^ i. 6
7 13