_{(przez czat )}

Pozycja OEIS A123321 wymienia ciąg liczb, które są iloczynem siedmiu różnych liczb pierwszych. Dla zwięzłości nazywamy to numerem 7DP . Kilka pierwszych liczb i odpowiadające im dzielniki znajdują się poniżej:

510510 = 2 * 3 * 5 * 7 * 11 * 13 * 17
570570 = 2 * 3 * 5 * 7 * 11 * 13 * 19
690690 = 2 * 3 * 5 * 7 * 11 * 13 * 23
746130 = 2 * 3 * 5 * 7 * 11 * 17 * 19

Wyzwanie polegać będzie na znalezieniu najbliższej liczby 7DP pod względem absolutnej odległości od danych wejściowych.

Wejście

Pojedyncza dodatnia liczba całkowita n w dowolnym dogodnym formacie .

Wynik

Najbliższa liczba 7DP do n , ponownie w dowolnym dogodnym formacie. Jeśli najbliższe są dwa numery 7DP, możesz wyprowadzić jeden lub oba.

Zasady

• Można założyć, że liczby mieszczą się w domyślnym [int]typie danych Twojego języka (lub równoważnym).
• Dopuszczalny jest pełny program lub funkcja.
• Standardowe luki są zabronione.
• To jest golf golfowy , więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod.

Przykłady

5 -> 510510
860782 -> 870870
1425060 -> 1438710 (or 1411410, or both)

Python, 89 86 85 bajtów

f=lambda n,k=0:126^sum(1>>n%i<<7*(n/i%i<1)for i in range(2,n))and f(n+k,k%2*2+~k)or n

Algorytm jest na początku O (przerażający), a rekurencja tak naprawdę nie pomaga, ale działa dobrze, dopóki n jest wystarczająco zbliżone do liczby 7DP.

Dzięki @xnor za grę w golfa z 3 bajtów!

Przetestować go na repl.it .

Jak to działa

Python nie ma wbudowanych funkcji pierwszeństwa ani faktoryzacji, ale możemy zidentyfikować liczby 7DP według ilości i charakteru ich dzielników.

Zgodnie z zasadą mnożenia liczbę dzielników liczby całkowitej można obliczyć jako iloczyn przyrostowych wykładników jej pierwszej faktoryzacji. Zatem σ ₀ (n) ( funkcja dzielnika ) wynosi 2 ^m za każdym razem, gdy n jest liczbą mDP.

σ ₀ (n) = 128 jest zatem warunkiem koniecznym, ale niewystarczającym; na przykład σ ₀ (2 ¹²⁷ ) = 128 , ale 2 ¹²⁷ wyraźnie nie jest liczbą 7DP. Jeśli jednak zarówno σ ₀ (n) = 128, jak i żaden idealny kwadrat nie dzieli równomiernie n , to n jest liczbą 7DP.

Dla wejścia n algorytm polega na sprawdzeniu liczb całkowitych n , n - 1 , n + 1 , n - 2 , n + 2 itd. I zwróceniu pierwszego, który jest liczbą 7DP.

Gdy f jest wywoływane z argumentem n , dzieje się tak:

• Kod

  126^sum(1>>n%i<<7*(n/i%i<1)for i in range(2,n))

  sprawdza, czy brak jest nie wiele 7DP następująco.

  Dla wszystkich liczb całkowitych i takie, że 1 <i <n , 1>>n%i<<7*(n/i%i<1)jest obliczany.

  • Jeśli n jest podzielne przez i, ale nie przez i ² , to 1>>n%idaje 1 i (n/i%i<1)daje 0 , co daje
    1,2 × ^0,0 = 1 .

  • Jeśli n jest podzielne przez i ² , 1>>n%ii (n/i%i<1)obie dają 1 , co daje 1,2 × ⁷ = 128 .

  • Jeśli n nie jest podzielne przez i , 1>>n%idaje 0 , co daje 0,2 ^{7 · x} = 0 .

  
  Suma liczb wynikających będzie 2 ^m - 2 , gdy n jest liczbą MDP (produkt 2 ^m dzielnikami, z wyłączeniem 1 i n ), a większa ilość niż 127. Jeśli brak jest kwadratem czynnik. Tak więc suma wyniesie 126 wtedy i tylko wtedy, gdy n jest liczbą 7DP.

• Dla liczb 7DP suma wynosi 126 , więc XOR z 126 daje 0 , co jest fałszem. W ten sposób, czy część lambda jest wykonany i f zwraca bieżące wartości n .

• Jeśli n nie jest liczbą 7DP, XOR zwróci niezerową, prawdziwą wartość. W ten sposób, a część lambda jest wykonywany.

  f(n+k,k%2*2+~k)

  rekurencyjnie wywołuje f ze zaktualizowanymi wartościami n (następny potencjalny numer 7DP) i k (różnica między nowym kandydatem a kolejnym).

  Jeśli k jest liczbą całkowitą nieujemną, k%2*2daje 0 i ~kdaje - (k + 1) . Suma obu wyników to - (k + 1) , która jest nieparzystą, ujemną liczbą całkowitą, która jest o 1 większa w wartości bezwzględnej niż k .

  Jeśli k jest nieparzystą, ujemną liczbą całkowitą, k%2*2daje 2, a ~kdaje - (k + 1) . Suma obu wyników wynosi 2 - (k + 1) = - (k - 1) , co jest parzystą, nieujemną liczbą całkowitą, która jest o 1 jednostkę większa w wartości bezwzględnej niż k .

  Oznacza to, że k przyjmuje wartości 0, -1, 2, -3, 4, ⋯ .

  Po dodaniu narastająco do n ₀ (wartość początkowa n ), wynikowe liczby całkowite to

  • n ₀ + 0
  • ( N ₀ + 0) - 1 n = ₀ - 1
  • ( n _0-1 ) + 2 = n ₀ + 1
  • ( n ₀ + 1) - 3 = n ₀ - 2
  • ( n _0–2 ) + 4 = n ₀ + 2
  • itp.

  
  upewniając się, że pierwsza liczba 7DP spotykamy jest tak blisko n ₀ , jak to możliwe.

Brachylog , 44 40 16 bajtów

_{Przekreślone 44 jest nadal regularne 44; (}

:I=+.>0,.$pPdPl7

Przykład:

?- run_from_atom(':I=+.>0,.$pPdPl7',1425060,Z).
Z = 1438710 .

Czy to możliwe, że ten język nie zawsze jest do kitu? Pokonałem Jelly i MATL!

Przypadek testowy z 5jest najdłuższy i zajmuje około 10 sekund na moim komputerze.

Byłoby to 12 bajtów, gdyby $pnie było błędu (nie potrzebowalibyśmy >0,.części)

Wyjaśnienie

Brachylog domyślnie używa programowania logiki ograniczeń dla całej arytmetyki liczb całkowitych. Co więcej, wbudowane etykietowanie =działa na prawdopodobnie nieskończonych domenach.

Że kolejno łączy zmienną bez ograniczeń (Tj (-inf, inf)) w następujący sposób: 0, 1, -1, 2, -2, 3, ….

Dlatego możemy uzyskać najbliższy numer 7DP, szukając pierwszego Izunifikowanego numeru (-inf, inf)(używając automatycznego cofania), dla którego Input + Ijest to numer 7DP.

:I=                Label variables in [Input, I]. I has no constraints and Input is known
   +.              Unify Output with Input + I
     >0,           Output > 0 (wouldn't be needed if $p failed for numbers less than 1)
        .$pP       Unify P with the list of prime factors of Output
            dP     Check that P with duplicates removed is still P
              l7   Check that the length of P is 7

Galaretka, 17 bajtów

Pµạ³,
×⁹ÆRœc7Ç€ṂṪ

Działa teoretycznie, ale jego ukończenie zajmuje wiele lat.

Oto wersja, która faktycznie działa dla danych wejściowych, ale teoretycznie nie działa w przypadku dużych danych wejściowych:

Pµạ³,
50ÆRœc7Ç€ṂṪ

Wypróbuj tutaj. To generuje wszystkie liczby pierwsze do 50, a następnie znajduje wszystkie 7 kombinacji liczb pierwszych na tej liście, a następnie wszystkie ich produkty. Wreszcie, po prostu znajduje najbliższy element z tej listy do podanego argumentu.

Oczywiście, gdy nasze 7DP zawierają liczby pierwsze większe niż 50, to się nie powiedzie. Wersja teoretyczna generuje wszystkie liczby pierwsze do 256n dla wejścia n , ale poza tym działa w ten sam sposób.

Dowód

Niech p(x)oznaczymy następną liczbę pierwszą po x. (Bardzo luźna) górna granica dla najbliższego produktu 7DP do x to:

p(x) * p(p(x)) * p(p(p(x))) * ... * p(p(p(p(p(p(p(x)))))))

Musimy tylko sprawdzić liczby pierwsze w [2… p (p (p (p (p (p (p (p (x))))))] . Postulat Bertranda mówi, że p (x) ≤ 2x , więc wystarczy sprawdzić wszystkie liczby pierwsze do 128x .

MATL , 21 17 16 14 13 bajtów

Podziękowania dla Dennisa za sugestię usunięcia 4 bajtów i kolejną, która pozwoliła zaoszczędzić jeszcze 1 bajt!

t17*Zq7XN!pYk

Działa to teoretycznie, ale zabraknie pamięci dla powyższych danych wejściowych 6(kompilator online).

Bardziej wydajna wersja wykorzystuje 21 bajtów i oblicza wszystkie przypadki testowe w ciągu około jednej sekundy:

t3e4/k16+_YqZq7XN!pYk

Wypróbuj online!

• Wersja nieefektywna pamięci
• Wersja wydajna pod względem pamięci
• Wersja wydajna pod względem pamięci, wszystkie przypadki testowe

Wyjaśnienie

Wersja wydajna pod względem pamięci

Weź przykład N = 860782. Wystarczy pod liczb pierwszych do M = 29, która jest najpierw pierwsza, że pomnożony przez 2*3*5*7*11*13przekracza N . W tym przykładzie 2*3*5*7*11*13*29 = 870870. Następna liczba pierwsza to 31. Jakikolwiek produkt obejmujący tę pierwszą lub większą będzie co najmniej 2*3*5*7*11*13*31 = 930930, a więc na pewno nie będzie rozwiązaniem, ponieważ przekracza to, 870870co przekracza N .

M jest obliczane jako pierwsza liczba pierwsza większa niż max(N/(2*3*5*7*11*13), 16). maxFunkcja jest stosowana w celu zapewnienia, że co najmniej 17jest zrywane. Aby zaoszczędzić kilka bajtów, zostaje zastąpiony przez kod 2*3*5*7*11*13 = 30030użytkownika 30000i funkcji maxprzez dodanie. Te zmiany są ważne, ponieważ dają większą wartość.

t      % Take input implicitly. Duplicate
3e4/k  % Divide input by 30000 and round down (rounding here is only needed
       % due to a bug in the "next prime" function)
16+    % Add 16
_Yq    % Next prime
Zq     % Prime numbers up to that value
7XN    % Combinations of those primes taken 7 at a time. Gives a 2D array
       % with each combination on a different row
!p     % Product of each row
Yk     % Output product that is closest to the input. Implicitly display

Wersja nieefektywna pamięci

Aby jeszcze bardziej zmniejszyć liczbę bajtów, podział można usunąć; w rzeczywistości wystarczy pomnożyć przez 17(dzięki, @Dennis). Zapewnia to uwzględnienie kolejnej liczby pierwszej (zgodnie z postulatem Bertranda ) i co najmniej wynik 17. Działa to teoretycznie, ale zabraknie pamięci dla danych wejściowych większych niż około 6.

W kodzie sekcja

3e4/k  % Divide input by 30000 and round down (rounding here is only needed
       % due to a bug in the "next prime" function)
16+    % Add 16
_Yq    % Next prime

zastępuje się przez

17*    % Multiply by 17

Pyke, 32 bajty

#PDl 7q.ID}lRlqi*(#)DF-X,)R],She

Wypróbuj tutaj!

Pamiętaj, że to nie działa online - limit czasu. Ta wersja sprawdza tylko 2 różne liczby pierwsze i powinna działać szybciej. Gdy dwie liczby w tej samej odległości znajdują się od celu, wybiera niższą.

Przechodzi przez wszystkie liczby, aż znajdzie taki, który jest większy niż wejście i ma wartość 7DP. Dla każdego numeru pozbywa się go, jeśli nie jest to 7DP. Następnie ma listę 7DP aż do wejścia z większym. Następnie wybiera ten, który jest najbliżej wejścia.

Julia, 59 bajtów

!n=sort(map(prod,combinations(17n|>primes,7))-n,by=abs)[]+n

To jest bardzo nieefektywne, ale działa w przypadku pierwszego przypadku testowego w praktyce, a dla pozostałych w teorii.

Kosztem kolejnych 5 bajtów - w sumie 64 bajtów - można znacznie poprawić wydajność.

!n=sort(map(prod,combinations(n>>14+17|>primes,7))-n,by=abs)[]+n

Wypróbuj online!

tło

Jak wspomniano w odpowiedzi @ LuisMendo , zestaw liczb pierwszych, które musimy wziąć pod uwagę dla najbliższej liczby 7DP, jest dość mały. Wystarczy, aby zestaw zawierał liczbę 7DP większą niż wartość wejściowa n , co będzie prawdą wtedy i tylko wtedy, gdy zawiera liczbę pierwszą p ≥ 17 taką, że 30300p = 2 · 3 · 5 · 7 · 11 · 13 · p ≥ n .

In On przedział zawierający co najmniej jedną liczbę pierwszą dowodzi, że przedział [x, 1,5x) zawiera co najmniej jedną liczbę pierwszą, ilekroć x ≥ 8 . Od 30030/16384 ≈ 1,83 , to znaczy, że musi być głównym P w (n / 30030 N / 16384) gdy n> 8 · 30300 = 242.400 .

Wreszcie, gdy n <510510 , p = 17 jest wyraźnie wystarczające, więc musimy wziąć pod uwagę liczby pierwsze do n / 16384 + 17 .

Kosztem wydajności możemy zamiast tego rozważyć liczby pierwsze do 17n . Działa to, gdy n = 1 i jest znacznie większe niż n / 16384 + 17 dla większych wartości n .

Jak to działa

17n|>primesoraz n>>14+17|>primes(przesunięcie bitów jest równoważne podzieleniu przez 2 ¹⁴ = 16384 ) oblicza przedziały liczb pierwszych wspomniane w poprzednim akapicie. Następnie combinations(...,7)oblicza wszystkie tablice siedmiu różnych liczb pierwszych w tym zakresie, a odwzorowanie prodna nich oblicza ich produkty, tj. Liczby 7DP, z których wybieramy odpowiedź.

Następnie -nodejmuje n prom dla każdej liczby 7DP, a następnie sort(...,by=abs)sortuje te różnice według ich wartości bezwzględnych. Na koniec wybieramy pierwszą różnicę za pomocą []i obliczamy odpowiedni numer 7DP, dodając n za pomocą +n.

Pyth, 30 bajtów

L&{IPbq7lPby#.W!syMH,hhZa0teZ,

Wypróbuj online!

Zestaw testowy.

(5 trwa zbyt długo)

Wyjaśnienie

L&{IPbq7lPby#.W!syMH,hhZa0teZ,

L&{IPbq7lPb     Defines a function y, whose argument is b:
 &                  Return if both the following are true:
  {IPb                  the prime factorization contains no duplicate; and:
      q7lPb             the number of prime factors is 7

           y#.W!syMH,hhZa0teZ,   The main programme. Input as Q.
                             ,QQ Implicit arguments, yield [Q,Q].
             .W                  While
               !syMH                   both numbers do not satisfy y:
                    ,hhZ             increment the first number
                          teZ        and decrement the second number
                        a0           while making it non-negative.

Mathematica 136 80 75 bajtów

Jest to proste podejście, działające na zewnątrz n.

njest 7-odrębnym produktem głównym, jeśli liczba czynników pierwszych wynosi 7 ( PrimeNu@#==7) i żaden z tych czynników nie pojawia się więcej niż jeden raz ( SquareFreeQ@#&).

g@n_:=(k=1;While[!(PrimeNu@#==7&&SquareFreeQ@#&)⌊z=n-⌊k/2](-1)^k⌋,k++];z)

Moje wcześniejsze zgłoszenie (136 bajtów) znalazło zarówno pierwszy 7-odrębny główny produkt powyżej, na jeśli istnieje, pierwszy 7-odrębny główny wynik poniżej n. Następnie po prostu określił, który był bliżejn . Jeśli produkty były w równej odległości, zwracane były oba.

Obecna wersja sprawdza n-1, n + 1, n-2, n + 2 ... aż osiągnie pierwszy 7-odrębny produkt główny. Ta bardziej wydajna wersja przyjmuje podejście Dennisa.

Kluczowym postępem było użycie ⌊k/2](-1)^k⌋do zwrócenia serii, 0, 1, -1, 2, -2 ... Zero służy do sprawdzenia, czy nsam jest produktem 7-odrębnym-pierwszym. Z tego powodu Floor(to znaczy ⌊...⌋) jest używane zamiast Ceiling.

g[5]
g[860782]
g[1425060]

510510

870870

1438710

05AB1E , 10 bajtów

°Åp7.ÆPs.x

Wypróbuj online!

Próbuje wszystkich kombinacji 7 z pierwszych 10 ** liczb pierwszych wejściowych. Skończy się pamięć dla wejść większych niż 1.

Znacznie bardziej wydajna 14-bajtowa wersja:

5°/7+Åp7.ÆPs.x

Wypróbuj online!

Wykorzystuje pierwsze liczby (wejściowe / 100000 + 7).