Wprowadzenie
Rozważ proces pobierania dodatniej liczby całkowitej n w pewnej bazie b i zastępowania każdej cyfry jej reprezentacją w podstawie cyfry po prawej stronie.
- Jeśli cyfra po prawej to 0, użyj podstawy b .
- Jeśli cyfra po prawej to 1, użyj unarskiego z zerami jako znakami sumy.
- Jeśli po prawej stronie nie ma cyfry (tzn. Jesteś w tym samym miejscu), zapętl się do najbardziej znaczącej cyfry.
Jako przykład niech n = 160 ib = 10. Uruchomienie procesu wygląda następująco:
The first digit is 1, the digit to the right is 6, 1 in base 6 is 1.
The next digit is 6, the digit to the right is 0, 0 is not a base so use b, 6 in base b is 6.
The last digit is 0, the digit to the right (looping around) is 1, 0 in base 1 is the empty string (but that's ok).
Concatenating '1', '6', and '' together gives 16, which is read in the original base b = 10.
Można również wykonać dokładnie tę samą procedurę, ale przesuwając w lewo zamiast w prawo :
The first digit is 1, the digit to the left (looping around) is 0, 0 is not a base so use b, 1 in base b is 1.
The next digit is 6, the digit to the left is 1, 6 in base 1 is 000000.
The last digit is 0, the digit to the left is 6, 0 in base 6 is 0.
Concatenating '1', '000000', and '0' together gives 10000000, which is read in the original base b = 10.
Tak więc stworzyliśmy dwie liczby związane ze 160 (dla b = 10): 16 i 10000000.
Zdefiniujemy n jako sprytną liczbę, jeśli równomiernie podzieli co najmniej jedną z dwóch liczb wygenerowanych w tym procesie na 2 lub więcej części
W przykładzie n jest przebiegły, ponieważ 160 dzieli 10000000 dokładnie 62500 razy.
203 NIE jest przebiegły, ponieważ wynikowe liczby to 2011 i 203, które 203 nie mogą równomiernie zmieścić się 2 lub więcej razy.
Wyzwanie
(W pozostałej części problemu rozważymy tylko b = 10.)
Wyzwanie polega na napisaniu programu, który znajdzie najwyższą podstępną liczbę, która jest również liczbą pierwszą.
Pierwsze 7 przebiegłych liczb pierwszych (i wszystko, co do tej pory znalazłem) to:
2
5
3449
6287
7589
9397
93557 <-- highest so far (I've searched to 100,000,000+)
Nie jestem oficjalnie pewien, czy jest ich więcej, ale spodziewam się, że tak. Jeśli możesz udowodnić, że jest ich wiele (lub nie ma ich wcale), dam ci +200 nagród.
Zwycięzcą zostanie osoba, która może zapewnić najwyższą podstępną liczbę pierwszą, pod warunkiem, że jest oczywiste, że byli aktywni w poszukiwaniu i nie celowo czerpią chwały od innych.
Zasady
- Możesz użyć dowolnego narzędzia do znajdowania najlepszych wyników.
- Możesz użyć probabilistycznych testerów pierwszych.
- Możesz ponownie użyć kodu innych osób z atrybutami . To wspólny wysiłek. Taktyki przełomu nie będą tolerowane.
- Twój program musi aktywnie wyszukiwać liczbę pierwszą. Możesz rozpocząć wyszukiwanie od najwyższej znanej podstępnej liczby pierwszej.
- Twój program powinien być w stanie obliczyć wszystkie znane sprytne liczby pierwsze w ciągu 4 godzin od wystąpienia Amazon EC2 t2.medium (cztery jednocześnie lub jedna przez cztery godziny lub coś pomiędzy nimi). Nie będę ich na nich testować, a ty na pewno nie musisz. To tylko punkt odniesienia.
Oto mój kod Python 3, którego użyłem do wygenerowania powyższej tabeli: (uruchamia się za sekundę lub dwie)
import pyprimes
def toBase(base, digit):
a = [
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'],
['', '0', '00', '000', '0000', '00000', '000000', '0000000', '00000000', '000000000' ],
['0', '1', '10', '11', '100', '101', '110', '111', '1000', '1001'],
['0', '1', '2', '10', '11', '12', '20', '21', '22', '100'],
['0', '1', '2', '3', '10', '11', '12', '13', '20', '21'],
['0', '1', '2', '3', '4', '10', '11', '12', '13', '14'],
['0', '1', '2', '3', '4', '5', '10', '11', '12', '13'],
['0', '1', '2', '3', '4', '5', '6', '10', '11', '12'],
['0', '1', '2', '3', '4', '5', '6', '7', '10', '11'],
['0', '1', '2', '3', '4', '5', '6', '7', '8', '10']
]
return a[base][digit]
def getCrafty(start=1, stop=100000):
for p in pyprimes.primes_above(start):
s = str(p)
left = right = ''
for i in range(len(s)):
digit = int(s[i])
left += toBase(int(s[i - 1]), digit)
right += toBase(int(s[0 if i + 1 == len(s) else i + 1]), digit)
left = int(left)
right = int(right)
if (left % p == 0 and left // p >= 2) or (right % p == 0 and right // p >= 2):
print(p, left, right)
if p >= stop:
break
print('DONE')
getCrafty()