Wprowadzenie
Twoim celem jest znalezienie najmniejszej liczby tych, które musisz dodać lub pomnożyć, aby uzyskać wartość wejściową, to A005245 .
Wkład
Jeden dodatnia N .
Wydajność
Najmniejsza liczba tych, które muszą być dodane / mnożone dostać N .
Przykładowe dane wejściowe
7
Przykładowe dane wyjściowe
6
Wyjaśnienie
(
1
+1
+1
) * (1
+1
) +1
= 7Ponieważ wymaga to
6
jednego, wynikiem jest6
Przypadki testowe
1 1
2 2
3 3
5 5
10 7
20 9
50 12
Ponieważ jest to wyzwanie związane z golfem , wygrywa najmniejsza liczba bajtów.
code-golf
sequence
arithmetic
integer
expression-building
Spyrali Chyuu
źródło
źródło
f(x) != x.primeFactorisation().sum()
z wyjątkiem 1?Odpowiedzi:
Python 2 ,
7470 bajtówWypróbuj online!
Wersja alternatywna, 59 bajtów (niezweryfikowana)
Działa to przynajmniej do n = 1 000 000 , ale muszę jeszcze udowodnić, że działa dla wszystkich dodatnich n .
Wypróbuj online!
źródło
n=a*j+b
zb<j
, ale możemy potrzebowaćb>=j
?b>=j
i drugieb>=a
. Ale masz rację, nie jest oczywiste, że tak się nie stanie.a*b+c*d
zea,b,c,d
wszystkimi wyrażeniami sumowania i są one bardzo wydajne.Galaretka ,
1614 bajtówDzięki Dennis za uratowanie 2 bajtów!
Wypróbuj online!
Wyjaśnienie logiczne
Biorąc pod uwagę liczbę n :
1
odpowiedź brzmi1
. Inaczej:Reprezentacja to albo,
a + b
alboa × b
gdziea
ib
są wyrażeniami.Rozważ wszystkie możliwe wartości
a
ib
:a + b
, wtedya
ib
są w zakresie[1 .. n-1]
.a × b
,a
ib
są odpowiednie dzielniki liczbyn
większe niż1
.W obu przypadkach lista
[[<proper divisors of n larger than 1>], [1, 2, ..., n-1]]
jest obliczana (ÆḌḊ,Ṗ
), zamapuj bieżący link na każdym numerze߀€
, dodaj poprawne pary razem (+U$
) i uzyskaj minimalną wartość (FṂo
).Wyjaśnienie kodu
źródło
JavaScript (ES6),
10896 bajtówBardzo nieefektywny;
Array(n>>1)
nieznacznie przyspiesza kosztem bajtu. Objaśnienie:n%++i
jest niezerowy, jeślii
nie jest czynnikiem, podobnien%++i/0
jestInfinity
(i dlatego jest prawdomówny, a także zdecydowanie nie minimalny), jeślii
nie jest czynnikiem, aleNaN
(a zatem fałszem), jeślii
jest czynnikiem. Edycja: Zapisano 12 bajtów z inspiracją z @ edc65.źródło
f(50)
ale niestety Windows Update uruchomił ponownie komputer, zanim mógł się skończyć.a
tablicę. Czy nie możesz scalić ocen w 2 lambdach i wziąć min?(i+=2)
innym,++i
więc oszczędzam w sumie 12 bajtów, dzięki!Pari / GP , 66 bajtów
Port odpowiedzi Pytona Dennisa :
Wypróbuj online!
Pari / GP , 72 bajty
Dłuższy, ale bardziej wydajny:
Wypróbuj online!
źródło
f(n)=vecmin(concat(n,[f(j)+f(n\j)+f(n%j)|j<-[2..n-1]]))
.Pari / GP , 213 bajtów
Edycja: Zostałem ciężko pobity .
Wypróbuj online!
źródło
Python 2 , 181 bajtów
Wypróbuj online!
źródło
f
nie może być anonimowa, ponieważ wywołuje się rekurencyjnie.Wolfram Language (Mathematica) , 59 bajtów
Zaoszczędzono 3 bajty dzięki Martinowi Enderowi. Korzystanie z kodowania CP-1252, gdzie
±
jest jeden bajt.Wypróbuj online!
źródło
±
zamiastf
zapisywania 3 bajtów przy założeniu, że źródło jest zakodowane w CP 1252: tio.run/##y00syUjNTSzJTE78///QRkNbQ@tDG/PirWx9M/…Perl 5 , -p 78 bajtów
79 bajtów w starym stylu liczenia (
+1
dla-p
)Fakt, że Perl musi korzystać z dodatkowego
$
dostępu do wszystkich skalarów, naprawdę szkodzi długości golfów, które wykonują dużo arytmetyki ...Ta metoda jest podobna do innych już opublikowanych (spróbuj pomnożyć i dodać, aby zbudować liczbę docelową, weź najtańszą). Jednak nie powtarza się wielokrotnie, więc można go używać do stosunkowo dużych nakładów.
Nie próbuje również zminimalizować kosztu budowy liczby przez dodanie lub zwielokrotnienie [lication, ponieważ perl 5 nie ma wbudowanego,
min
a sortowanie numeryczne jest dłuższe (jak widać z sortowania wciąż w kodzie). Zamiast tego zakładam tylko, czy liczba jest czynnikiem celu, którego użyję mnożenia. Jest to bezpieczne, ponieważ jeśli np.3
Jest czynnikiem12
(więc sumuje koszt3
i12/3
) później w pętli, rozważy,9=12-3
który nie będzie czynnikiem, więc9+3
przy takim samym koszcie, jak3+9
i tak zostanie wypróbowany. Może to jednak nie powieść się w przypadku celów<= 4
(dotyczy to tylko1
i2
). Dodanie$_
do listy w celu zminimalizowania naprawia to. Co jest niefortunne, ponieważ tak naprawdę nie potrzebuję tego w przypadku bazowych przypadków, ponieważ już zainicjowałem@;
z prawidłowymi wartościami początkowymi, więc kosztuje 3 bajty.Wypróbuj online!
źródło