Sopfr
Programiści dopisali, pokonując zadanie z poprzedniego wpisu. Na palmę pierwszeństwa zasługuje zwłaszcza Antyp1958, który rozprawił się z problemem totalnie. Ustalił, że w uogólnionym ciągu Fibonacciego liczba pierwsza debiutuje na miejscu 1610 i liczy 340 cyfr, jeśli na starcie są dwie liczby złożone względnie pierwsze 1936 i 3349. Ten ciąg już czternastym wyrazem mija milion: 1936, 3349, 5285, 8634, 13919, 22553, 36472, 59025, 95497, 154522, 250019, 404541, 654560, 1059101,… Ostatnia liczba tej czołówki jest półpierwsza (263*4027) i tylko o 2 ustępuje pierwszej.
Warto zauważyć, że wielu rozwiązujących milcząco zakładało, że druga liczba startowa musi być większa od pierwszej, a takiego warunku w zadaniu nie było.
Dziś jeszcze jeden problem typowo programistyczny (przyrzekam, że ostatni w tym roku) – bardzo podobny do poprzedniego, ale trudniejszy. Tym razem przyjmujemy, że ciąg tworzą tylko liczby złożone, więc jest on skończony – finał stanowi pojawiająca się w nim liczba pierwsza. W podstawowej formie ciąg zaczyna najmniejsza liczba złożona i liczy on tylko 4 wyrazy:
4, 8, 14, 23.
Startując od 60 udaje się dotrzeć dwukrotnie dalej:
60, 72, 84, 98, 114, 138, 166, 251.
A zadanie polega na ustaleniu jaki ciąg jest najdłuższy przy ograniczeniu zakresu liczby początkowej do 1000?
Ciągiem rządzi następująca reguła: każdy kolejny wyraz jest sumą poprzedniego wyrazu i sumy jego wszystkich (nie tylko różnych) czynników pierwszych.
Bez ograniczenia pierwszością ciąg w podstawowej formie jest w OEIS (A096461).
Wypada jeszcze wyjaśnić dziwny tytuł tego wpisu. Sopfr(n) to skrótowe anglojęzyczne oznaczenie addytywnej funkcji teorioliczbowej równej sumie wszystkich czynników pierwszych liczby n (sum of prime factors with repetitions).
Komentarze z prawidłowym rozwiązaniem ujawniane są wieczorem w przeddzień kolejnego wpisu (z błędnym zwykle od razu). Wpisy pojawiają się co 7 dni.
Komentarze
Dopisek do poprzedniego wpisu:
Najlepsza para ≤20000: a0=8750, a1=417
Indeks pierwszej liczby pierwszej: 2894
Liczba cyfr: 609
Liczba pierwsza:
168277753500984979241582085814561964128513484646587462162340776296403669144910288909781348842480000624379346601885960776819677582829706893025895597579446411517969756064405075183375301457855305507962411367841364734318856082899881375550491888355044178759529568095755602746503209603221251946939446328020393204065944344440517150960903161941630376911752386773907133804285555398095725916677704585413101641953579381688109057705407091393661273717255187837727677480025252967311556593634348513085947540532612916454057117020680645578888179036539904696469284312583941242613786342130668609372283769409560317068654103384439
Każdą kandydatkę na „pierwszą” sprawdzałem dwuetapowo — szybkie dzielenie przez małe liczby pierwsze (2,3,5,7,….) + test Millera–Rabina.
Ten problem jest banalny w porównaniu do poprzedniego. Najdłuższy ciąg (liczymy łącznie z kończącą go liczbą pierwszą), przy starcie ≤ 1000, zaczyna się od 183 i ma 21 wyrazów:
183, 247, 279, 316, 399, 428, 539, 564, 618, 726, 753, 1007, 1079, 1175, 1232, 1258, 1314, 1395, 1437, 1919, 2039.
Kilku następnych „liderów”:
start 886 → długość 20, finał 5021,
start 247 → długość 20, finał 2039,
start 328 → długość 19, finał 2039,
start 279 → długość 19, finał 2039.
Wszystkie wyrazy aż do ostatniego są złożone, a ciąg kończy się na pierwszej napotkanej liczbie pierwszej.
Tu jest prosty program w Pascalu, który znajduje:
program NajdluzszyCiag_SOPrf_1000;
{$A+,B-,D-,E-,F-,I-,L-,N-,O-,R-,S-,V-}
{ a_(n+1) = a_n + sopfr(a_n),
gdzie sopfr(n) = suma wszystkich czynników pierwszych n z krotnościami.
Szukamy startu (złożonego) <= 1000, który daje najdłuższy ciąg
zakończony pierwszą napotkaną liczbą pierwszą. }
function IsPrime(n: LongInt): Boolean;
var
i: LongInt;
begin
if n < 2 then begin IsPrime := False; Exit; end;
if (n = 2) or (n = 3) then begin IsPrime := True; Exit; end;
if (n mod 2 = 0) or (n mod 3 = 0) then begin IsPrime := False; Exit; end;
i := 5;
while i * i <= n do
begin
if (n mod i = 0) or (n mod (i + 2) = 0) then begin IsPrime := False; Exit; end;
i := i + 6;
end;
IsPrime := True;
end;
function SumOfPrimeFactors(n: LongInt): LongInt;
var
s, p: LongInt;
begin
{ suma czynników pierwszych z krotnościami }
s := 0;
{ czynniki 2 }
while (n mod 2 = 0) do
begin
s := s + 2;
n := n div 2;
end;
{ czynniki nieparzyste }
p := 3;
while p * p 1 }
if n > 1 then s := s + n;
SumOfPrimeFactors := s;
end;
procedure CiagInfo(start: LongInt; var dlugosc: LongInt; var ostatnia: LongInt);
var
a, nxt: LongInt;
begin
a := start;
dlugosc := 1; { liczymy od startu }
while not IsPrime(a) do
begin
nxt := a + SumOfPrimeFactors(a);
a := nxt;
Inc(dlugosc);
end;
ostatnia := a; { pierwsza napotkana liczba pierwsza }
end;
var
bestStart, bestLen: LongInt;
bestLast: LongInt;
s, len, last: LongInt;
function IsComposite(x: LongInt): Boolean;
begin
IsComposite := (x > 3) and (not IsPrime(x));
end;
begin
bestStart := -1;
bestLen := -1;
bestLast := -1;
for s := 4 to 1000 do
begin
if IsComposite(s) then
begin
CiagInfo(s, len, last);
if len > bestLen then
begin
bestLen := len;
bestStart := s;
bestLast := last;
end;
end;
end;
WriteLn(‚Najdluzszy ciag dla startu <= 1000:');
WriteLn('Start: ', bestStart);
WriteLn('Dlugosc (z ostatnia liczba pierwsza): ', bestLen);
WriteLn('Koncowa liczba pierwsza: ', bestLast);
Readln;
end.
Najwięcej, bo 21 wyrazów, jest w tym ciągu
183, 247, 279, 316, 399, 428, 539, 564, 618, 726, 753, 1007, 1079, 1175, 1232, 1258, 1314, 1395, 1437, 1919, 2039
21 => 183, …, 2039
23 => 1102, …, 5021
28 => 1414, …, 9311
29 => 5708, …, 35111
31 => 6033, …, 82219
34 => 7852, …, 82219
37 => 9388, …, 82219
42 => 12512, …, 89809
45 => 13492, …, 181421
51 => 45634, …, 885839
59 => 71462, …, 420899
60 => 79204, …, 420899
65 => 104462, …, 3269039
66 => 104775, …, 3269039
75 => 134884, …, 1963799
100 => 137222, …, 35200439
123 => 152898, …, 35200439
124 => 153633, …, 35200439
183
Dla startów ≤ 1000 największą liczbąpierwszą na końcu ciągu jest9.
Najmniejszy start, który do niej dochodzi, to 855 (długość ciągu: 18).
Pełny ciąg dla startu 855:
855, 885, 952, 982, 1475, 1544, 1743, 1836, 1866, 2182,
3275, 3416, 3490, 3846, 4492, 5619, 7495, 8999
Do 8999 dochodzą też inne starty ≤1000:
885 (17 wyrazów),
952 (16 wyrazów),
982 (15 wyrazów).
—————————————————————————-
Dla startów ≤ 10 000 najdłuższy ciąg (zakończony liczbą pierwszą) zaczyna się od 9388, ma 37 wyrazów i kończy się na 82219. Oto wszystkie elementy:
1: 9388
2: 11739
3: 11805
4: 12600
5: 12629
6: 12875
7: 12993
8: 13128
9: 13684
10: 14010
11: 14487
12: 14940
13: 15038
14: 15216
15: 15544
16: 15646
17: 23471
18: 23964
19: 25968
20: 26520
21: 26564
22: 26826
23: 27111
24: 28412
25: 35519
26: 38759
27: 38893
28: 39024
29: 39309
30: 52415
31: 53384
32: 60063
33: 80087
34: 80784
35: 80829
36: 82125
37: 82219 ← liczba pierwsza (koniec)
————————————————————-
Dla ograniczenia startu do 10 000 największą liczbę pierwszą na końcu ciągu daje start:
start: 9 722
długość ciągu: 27
końcowa liczba pierwsza: 268 439
Pełny ciąg od 9 722 (ostatni wyraz jest pierwszy, reszta złożone):
9722, 14585, 17507, 17616, 17994, 20998, 31499, 33935, 34568,
34752, 34948, 43689, 58255, 58512, 58599, 59005, 70811, 71256,
74234, 111353, 111608, 113614, 170423, 185927, 212495, 254999, 268439
Wśród startów złożonych ≤ 10 000 tylko 9 722 osiąga tę maksymalną liczbę pierwszą.
——————————————————————————————
Najdłuższy ciąg (liczony łącznie z kończącą go liczbą pierwszą) dla startu ≤ 100 000 ma 60 wyrazów. Najmniejszy start, który go daje, to 79204, a finałem jest liczba pierwsza 420 899.
start 79204 → długość 60 → finał 420 899
Są jeszcze dwa inne starty dające tę samą maksymalną długość 60 i ten sam finał:
start 98 745 → długość 60 → finał 420 899
start 99 778 → długość 60 → finał 420 899
Wszystkie liczby ciągu:
1: 79204
2: 99009
3: 99230
4: 109160
5: 111900
6: 120984
7: 128238
8: 145389
9: 145560
10: 156528
11: 161340
12: 166374
13: 175299
14: 175314
15: 184689
16: 185262
17: 197916
18: 202860
19: 210654
20: 217677
21: 221346
22: 229926
23: 232878
24: 240426
25: 241902
26: 252639
27: 257157
28: 262479
29: 265779
30: 269226
31: 271059
32: 282201
33: 286659
34: 291729
35: 294459
36: 300249
37: 305229
38: 308889
39: 312657
40: 316377
41: 326061
42: 327291
43: 333606
44: 337098
45: 343122
46: 351669
47: 355074
48: 365610
49: 372066
50: 376242
51: 382809
52: 388929
53: 393717
54: 400191
55: 400453
56: 401256
57: 406841
58: 414363
59: 418086
60: 420899 ← liczba pierwsza, koniec
Dla startów (liczby złożone) ≤ 100 000 największą liczbę pierwszą na końcu ciągu daje start:
start: 84 844
długość ciągu: 53
końcowa liczba pierwsza: 1 734 511
1: 84844
2: 106059
3: 141415
4: 169703
5: 170687
6: 171020
7: 171549
8: 171958
9: 172764
10: 177573
11: 178182
12: 178941
13: 181104
14: 181584
15: 182244
16: 183621
17: 184116
18: 184968
19: 185784
20: 186519
21: 187821
22: 188394
23: 189111
24: 189804
25: 190626
26: 191343
27: 192069
28: 192657
29: 193458
30: 194334
31: 195063
32: 196179
33: 197112
34: 197808
35: 198717
36: 199572
37: 200421
38: 201126
39: 201726
40: 203097
41: 204126
42: 205533
43: 206367
44: 207708
45: 208869
46: 210096
47: 210828
48: 212259
49: 214068
50: 216021
51: 226071
52: 227751
53: 1734511 ← liczba pierwsza (koniec)
Kolejne rekordy:
126 => 1547306, …, 82216501
127 => 1549600, …, 82216501
133 => 1567122, …, 82216501
134 => 1775718, …, 82216501
137 => 3405250, …, 71927183
144 => 6686828, …, 10176993857
146 => 7154132, …, 10176993857
193 => 8107371, …, 4773997451
194 => 12587663, …, 1336832221
217 => 13161303, …, 31760920439
234 => 33543782, …, 27738914183
254 => 42535278, …, 27738914183
Zakres: liczba początkowa <= 100M
Kto rozwiązał zadanie z tego tygodnia, ten – przy niewielkiej modyfikacji kodu – znajdzie zapewne odpowiedź na pytanie dodatkowe. Chodzi o policzenie, ile najwięcej wyrazów danego ciągu (z zakresu do tysiąca) jest liczbami półpierwszymi, mającymi dokładnie dwa dzielniki. I który to jest ciąg?
To samo pytanie dotyczy zakresu do 10000. Tam należy odnaleźć lidera i wicelidera.
A oto odpowiedzi na pytania, które wcześniej zadałem.
Zakres do 1000, to jedyne wystąpienie, bo wszystkie inne są mniejsze. Pierwsza liczba w ciągu to ilość liczb tego ciągu z ostatnią liczbą pierwszą. Druga liczba (w nawiasie) to ilość liczb półpierwszych w tym ciągu.
18 [8] => 314, 473, 527, 575, 608, 637, 664, 753, 1007, 1079, 1175, 1232, 1258, 1314, 1395, 1437, 1919, 2039
Zakres do 10000. Dla obu przykładów są to jedyne wystąpienia z taką, maksymalną ilością liczb półpierwszych.
21 [11] => 5587, 5775, 5806, 8711, 9023, 10319, 10943, 11327, 11615, 11744, 12121, 12192, 12332, 15419, 16343, 16679, 17975, 18704, 18886, 18985, 22787
27 [12] => 9722, 14585, 17507, 17616, 17994, 20998, 31499, 33935, 34568, 34752, 34948, 43689, 58255, 58512, 58599, 59005, 70811, 71256, 74234, 111353, 111608, 113614, 170423, 185927, 212495, 254999, 268439
W konkurencji „pierwszy element <=1000", wygrywa ciąg:
[183, 247, 279, 316, 399, 428, 539, 564, 618, 726, 753, 1007, 1079, 1175, 1232, 1258, 1314, 1395, 1437, 1919, 2039], mający 21 elementów.
263 => 215681866, …, 33207501563
Przeszukane ciągi z liczbą początkową do 240M
296 => 268566556, …, 108120775871
297 => 270906418, …, 108120775871
302 => 282656395, …, 108120775871
306 => 309689698, …, 108120775871
Przeszukane ciągi z liczbą początkową do 350M
307 => 582916275, …, 169359097057
Przeszukane ciągi z liczbą początkową do miliarda
Pytanie grgkh:
Zwycięzca (najwięcej liczb półpierwszych) dla<=1000 to 314 (prawie pi*100)
liczba półpierwszych (przed finałową liczbą pierwszą): 8
długość ciągu (z finałem): 18
ostatni wyraz (liczba pierwsza): 2039
Ciąg od 314:
314, 473, 527, 575, 608, 637, 664, 753, 1007, 1079, 1175, 1232, 1258, 1314, 1395, 1437, 1919, 2039
Półpierwsze w tym ciągu (z rozkładami):
314 = 2×157, 473 = 11×43, 527 = 17×31, 753 = 3×251,
1007 = 19×53, 1079 = 13×83, 1437 = 3×479, 1919 = 19×101.
Drugie miejsce
Jest sporo pozycji z taką samą ilością półpierwszych; najmniejszy start z drugą najwyższą liczbą półpierwszych (= 7) to:
start: 183
liczba półpierwszych: 7
długość ciągu (z finałem): 21
ostatni wyraz (liczba pierwsza): 2039
Ciąg od 183:
183, 247, 279, 316, 399, 428, 539, 564, 618, 726, 753, 1007, 1079, 1175, 1232, 1258, 1314, 1395, 1437, 1919, 2039
Półpierwsze w tym ciągu:
183 = 3×61, 247 = 13×19, 753 = 3×251, 1007 = 19×53,
1079 = 13×83, 1437 = 3×479, 1919 = 19×101.
Inne starty z wynikiem 7 (dla pełności): 328, 344, 375, 378, 393, 396, 417, 427, 473 (wszystkie kończą na 2039) oraz 974 (kończy na 3671).
_______________________________________________________
Dla startów (złożonych) <= 10 000:
1. Najwięcej liczb półpierwszych dla : 9 722
liczba półpierwszych (przed finałową liczbą pierwszą): 12
długość ciągu (z finałem): 27
ostatni wyraz (liczba pierwsza): 268 439
Półpierwsze w tym ciągu (pozycja → liczba = rozkład):
1 → 9 722 = 2×4 861
2 → 14 585 = 5×2 917
6 → 20 998 = 2×10 499
7 → 31 499 = 13×2 423
12 → 43 689 = 3×14 563
16 → 59 005 = 5×11 801
19 → 74 234 = 2×37 117
22 → 113 614 = 2×56 807
23 → 170 423 = 11×15 493
24 → 185 927 = 7×26 561
25 → 212 495 = 5×42 499
26 → 254 999 = 19×13 421
2. Drugie miejsce
start: 5 587
liczba półpierwszych: 11
długość ciągu (z finałem): 21
ostatni wyraz (liczba pierwsza): 22 787
Półpierwsze w tym ciągu:
1 → 5 587 = 37×151
3 → 5 806 = 2×2 903
4 → 8 711 = 31×281
5 → 9 023 = 7×1 289
6 → 10 319 = 17×607
7 → 10 943 = 31×353
8 → 11 327 = 47×241
14 → 15 419 = 17×907
15 → 16 343 = 59×277
16 → 16 679 = 13×1 283
20 → 18 985 = 5×3 797
_____________________________________________________
Najwięcej liczb półpierwszych (iloczyn dwóch liczb pierwszych, z krotnościami; np. P^2 też się liczy) w ciągu dla startów <= 100000 daje start:
start: 73 913 (złożona)
liczba liczb półpierwszych w ciągu: 20
liczba wyrazów złożonych (do pierwszej napotkanej pierwszej): 43
ostatni wyraz (liczba pierwsza kończąca ciąg): 927 287
długość całego ciągu (z finałową pierwszą): 44
Są remisy: tę samą maksymalną liczbę półpierwszych (=20) i ten sam finał 927 287 dają jeszcze starty: 77 429, 82 673, 83 693, 83 849 (wszystkie z długością 44).
Rekordowy ciąg (start 73 913)
Cały ciąg :
73913, 84479, 88175, 91712, 93157, 98079, 130775, 136016, 144525, 144626, 216941, 217883, 222047, 253775, 263936, 264983, 286967, 312797, 265469, 269279, 286631, 295787, 305291, 317291, 330623, 331157, 335219, 339629, 358043, 394119, 395466, 398959, 435239, 435984, 436319, 469895, 563879, 565439, 646223, 651287, 651745, 782099, 807359, 927287
poniżej pełne rozkłady 20 liczb półpierwszych występujących w rekordowym ciągu (start 73 913, długość 44, finał 927 287). Podaję też pozycję w ciągu (licząc od startu):
poz. 1: 73 913 = 7 × 10 559
poz. 2: 84 479 = 23 × 3 673
poz. 5: 93 157 = 19 × 4 903
poz. 6: 98 079 = 3 × 32 693
poz. 10: 144 626 = 2 × 72 313
poz. 11: 216 941 = 401 × 541
poz. 12: 217 883 = 53 × 4 111
poz. 13: 222 047 = 7 × 31 721
poz. 18: 265 469 = 71 × 3 739
poz. 19: 269 279 = 113 × 2 383
poz. 31: 398 959 = 11 × 36 269
poz. 34: 436 319 = 13 × 33 563
poz. 35: 469 895 = 5 × 93 979
poz. 36: 563 879 = 569 × 991
poz. 37: 565 439 = 7 × 80 777
poz. 38: 646 223 = 131 × 4 933
poz. 40: 651 745 = 5 × 130 349
poz. 41: 782 099 = 31 × 25 229
poz. 42: 807 359 = 7 × 115 337
poz. 43: 922 703 = 211 × 4 373
318 => 1403003209, …, 1998287767061
392 => 1492889682, …, 1291083950993
409 => 1625681044, …, 1291083950993
Przeszukane ciągi z liczbą początkową do 1750M
Zadanie grgkh (do 10000):
lider 9722
wicelider 5587
Best starting number (≤1000): 183
Length of sequence: 20
Sequence:
[183, 247, 279, 316, 399, 428, 539, 564, 618, 726, 753, 1007, 1079, 1175, 1232, 1258, 1314, 1395, 1437, 1919]
Z poprawka na liczbę pierwszą zatrzymującą znaleziony ciąg:
Best starting number (≤1000): 183
Length of sequence: 21
Sequence:
[183, 247, 279, 316, 399, 428, 539, 564, 618, 726, 753, 1007, 1079, 1175, 1232, 1258, 1314, 1395, 1437, 1919, 2039]
412 => 2170362028, …, 1291083950993
413 => 2323372431, …, 1291083950993
470 => 3800328758, …, 89063744493211
472 => 4633219076, …, 89063744493211
483 => 4654839027, …, 89063744493211
Przeszukane ciągi z liczbą początkową do 7,77G
Jezus Maria, końca nie widać! 🙂
mp
Kolejny raz otrzymałem wsparcie od Eryka programisty, któremu wyszło, że jak zaczniemy od 183, to dojdziemy do 2039, ciąg ma 21 wyrazów.
pierwszy element <=1000
długość ciągu = 21
ciąg = [183, 247, 279, 316, 399, 428, 539, 564, 618, 726, 753, 1007, 1079, 1175, 1232, 1258, 1314, 1395, 1437, 1919, 2039]
pierwszy element <=10000
długość ciagu = 37
ciąg = [9388, 11739, 11805, 12600, 12629, 12875, 12993, 13128, 13684, 14010, 14487, 14940, 15038, 15216, 15544, 15646, 23471, 23964, 25968, 26520, 26564, 26826, 27111, 28412, 35519, 38759, 38893, 39024, 39309, 52415, 53384, 60063, 80087, 80784, 80829, 82125, 82219]
pierwszy element <=100000 (trzech zwycięzców)
długość ciagu = 60
ciąg_1 = [79204, 99009, 99230, 109160, 111900, 112290, 112516, 113766, 114121, 114289, 114888, 119684, 149609, 149780, 157278, 159677, 182495, 182649, 183328, 183692, 186132, 201650, 201808, 214429, 223775, 232736, 233792, 234098, 235914, 236104, 238804, 239298, 279186, 279320, 286314, 286744, 287314, 288894, 289529, 290639, 291719, 294143, 296999, 297408, 298972, 300840, 300986, 322494, 323469, 323885, 324408, 326355, 348120, 349104, 350161, 400191, 400453, 401256, 406841, 420899]
ciąg_2 = [98745, 99009, 99230, 109160, 111900, 112290, 112516, 113766, 114121, 114289, 114888, 119684, 149609, 149780, 157278, 159677, 182495, 182649, 183328, 183692, 186132, 201650, 201808, 214429, 223775, 232736, 233792, 234098, 235914, 236104, 238804, 239298, 279186, 279320, 286314, 286744, 287314, 288894, 289529, 290639, 291719, 294143, 296999, 297408, 298972, 300840, 300986, 322494, 323469, 323885, 324408, 326355, 348120, 349104, 350161, 400191, 400453, 401256, 406841, 420899]
ciąg_3 = [99778, 106914, 107195, 109160, 111900, 112290, 112516, 113766, 114121, 114289, 114888, 119684, 149609, 149780, 157278, 159677, 182495, 182649, 183328, 183692, 186132, 201650, 201808, 214429, 223775, 232736, 233792, 234098, 235914, 236104, 238804, 239298, 279186, 279320, 286314, 286744, 287314, 288894, 289529, 290639, 291719, 294143, 296999, 297408, 298972, 300840, 300986, 322494, 323469, 323885, 324408, 326355, 348120, 349104, 350161, 400191, 400453, 401256, 406841, 420899]
pierwszy element <=1000000
długość ciągu = 124
Przeszukałem wszystkie ciągi z liczbą początkową do 10 miliardów. Niczego więcej nie znalazłem.
Odnotowywałem tylko ciągi bijące (a nie wyrównujące) rekord długości, począwszy od rekordzisty dla tysiąca.
499 => 14979762494, …, 272346708030599
Przeszukane ciągi do 15 miliardów.
Nareszcie pięćsetka pękła …
505 => 18401711762, …, 272346708030599