Równość przychodzi w trójkach

11

Zaczerpnięte z: OEIS- A071816

Twoim zadaniem, biorąc pod uwagę górną granicę n, jest znalezienie liczby rozwiązań, które spełniają równanie:

a+b+c = x+y+z, where 0 <= a,b,c,x,y,z < n

Sekwencja zaczyna się zgodnie z opisem na stronie OEIS i jak poniżej (1-indeksowany):

1, 20, 141, 580, 1751, 4332, 9331, 18152, 32661, 55252, 88913, 137292, 204763, 296492, 418503, 577744, 782153, 1040724, 1363573, 1762004, 2248575, 2837164, 3543035, 4382904, 5375005, 6539156, 7896825, 9471196, 11287235, 13371756

Ponieważ n = 1istnieje tylko jedno rozwiązanie:(0,0,0,0,0,0)

Dla n = 2istnieją 20 zamawiane rozwiązania (a,b,c,x,y,z)do a+b+c = x+y+z:

(0,0,0,0,0,0), (0,0,1,0,0,1), (0,0,1,0,1,0), (0,0,1,1,0,0), (0,1,0,0,0,1), 
(0,1,0,0,1,0), (0,1,0,1,0,0), (0,1,1,0,1,1), (0,1,1,1,0,1), (0,1,1,1,1,0), 
(1,0,0,0,0,1), (1,0,0,0,1,0), (1,0,0,1,0,0), (1,0,1,0,1,1), (1,0,1,1,0,1), 
(1,0,1,1,1,0), (1,1,0,0,1,1), (1,1,0,1,0,1), (1,1,0,1,1,0), (1,1,1,1,1,1).

I & O

  • Dane wejściowe oznaczają pojedyncze liczby całkowite n.
  • Dane wyjściowe to pojedyncza liczba całkowita / ciąg znaków f(n), gdzie f(...)jest funkcja powyżej.
  • Indeksowanie jest dokładnie takie, jak opisano, żadne inne indeksowanie nie jest dopuszczalne.

To jest , wygrana o najniższej liczbie bajtów.

Urna Magicznej Ośmiornicy
źródło
Ahhh crappp, nie zauważyłem bezpośredniej formuły OEIS, myślałem, że to nie będzie takie proste. No cóż, nie daję +1 bezpośrednim portom tego równania; P.
Magic Octopus Urn
1
Przynajmniej formuła nie była idealnie golfowa: P
fəˈnɛtɪk
Z drugiej strony daje reg-langs szansę przeciwko eso-langs.
Magic Octopus Urn
Czy byłoby lepiej, gdyby tytuł brzmiał „równość przychodzi w trojaczkach”?
Leaky Nun

Odpowiedzi:

11

Galaretka , 9 6 bajtów

ṗ6ḅ-ċ0

Roztwór O (n 6 ) .

Wypróbuj online!

Jak to działa

ṗ6ḅ-ċ0  Main link. Argument: n

ṗ6      Cartesian power 6; build all 6-tuples (a, x, b, y, c, z) of integers in
        [1, ..., n]. The challenge spec mentions [0, ..., n-1], but since there
        are three summands on each side, this doesn't matter.
  ḅ-    Unbase -1; convert each tuple from base -1 to integer, mapping (a, ..., z)
        to a(-1)**5 + x(-1)**4 + b(-1)**3 + y(-1)**2 + c(-1)**1 + z(-1)**0, i.e.,
        to -a + x - b + y - c + z = (x + y + z) - (a + b + c). This yields 0 if and
        only if the 6-tuple is a match.
    ċ0  Count the number of zeroes.
Dennis
źródło
Ha! Uwielbiam teoretyczne odpowiedzi (moja podstawa teoretycznej odpowiedzi brzmi teraz, czy działa ona na TIO dla dużych wartości n , prawdopodobnie jest to złe). Miałem nadzieję zobaczyć O(n^6)chociaż: P.
Magic Octopus Urn
9

Mathematica 17 lub 76 bajtów

Za pomocą wzoru:

.55#^5+#^3/4+#/5&

(Zapisano 3 bajty na @GregMartin i @ngenisis)

Zamiast używać formuły, tutaj dosłownie obliczam wszystkie rozwiązania i je liczę.

Length@Solve[a+b+c==x+y+z&&And@@Table[(0<=i<#),{i,{a,b,c,x,y,z}}],Integers]&
Kelly Lowder
źródło
2
Dzięki za opublikowanie postu bez użycia siły :). +1 za każdą odpowiedź matematyczną, która nie jest równaniem ani nie jest wbudowana.
Magic Octopus Urn
Jak na tej odpowiedzi , można zastąpić 11/20przez .55do oszczędności dwu-bajtowych.
Greg Martin
Nie potrzebujesz również gwiazdki w pierwszym okresie.
ngenisis
8

Haskell , 48 bajtów

Nie zauważyłem formuły przed napisaniem tego, więc zdecydowanie nie jest to najkrótsza (lub najszybsza) ogólna metoda, ale myślałem, że była ładna.

f n=sum[1|0<-foldr1(-)<$>pure[1..n]`mapM`[1..6]]

Wypróbuj online!

f ngeneruje wszystkie listy 6 elementów [1..n], a następnie zlicza te, których suma naprzemienna wynosi 0. Wykorzystuje fakt, który a+b+c==d+e+fjest taki sam jak a-(d-(b-(e-(c-f))))==0, a także, że nie ma znaczenia, jeśli dodamy 1 do wszystkich liczb.

Ørjan Johansen
źródło
Zauważyłem, że często najkrótsza odpowiedź jest najmniej imponująca;). Jest to całkiem fajne zastosowanie fold, którego nie wziąłbym pod uwagę przed zobaczeniem tej odpowiedzi.
Magic Octopus Urn
6

MATL , 12 bajtów

l6:"G:gY+]X>

Wypróbuj online!

Wyjaśnienie

Nie mogłem przegapić okazji do ponownego użycia splotu!

Wykorzystuje to następującą charakterystykę z OEIS:

a(n) = largest coefficient of (1+...+x^(n-1))^6

i oczywiście mnożenie wielomianowe to splot.

l        % Push 1
6:"      % Do the following 6 times
  G:g    %   Push a vector of n ones, where n is the input
  Y+     %   Convolution
]        % End
X>       % Maximum
Luis Mendo
źródło
5

Galaretka , 9 bajtów

ṗ3S€ĠL€²S

Nie tak krótki jak @ Dennis's, ale kończy się w mniej niż 20 sekund na wejście 100.

Wypróbuj online!

Jak to działa

ṗ3S€ĠL€²S  Main link. Argument: n

ṗ3         Cartesian power; yield all subsets of [1, ..., n] of length 3.
  S€       Sum each. 
    Ġ      Group indices by their values; for each unique sum S, list all indices whose
           values are equal to S.
     L€    Length each; for each unique sum S, yield the number of items in the original
           array that sum to S.
       ²   Square each; for each unique sum S, yield the number of pairs that both sum to S.
        S  Sum; yield the total number of equal pairs.
ETHprodukcje
źródło
Czy możesz wyjaśnić tę metodę? Obecnie uczę się galaretki, ale wciąż nie jestem wystarczająco dobry, aby udzielić prawdziwych odpowiedzi; Zawsze szukam dobrych przykładów, Dennis i kilku innych.
Magic Octopus Urn
@carusocomputing Ukończono wyjaśnienie. Daj mi znać, jeśli nadal masz jakieś pytania :-)
ETHproductions
Niesamowite, w większości jestem zdezorientowany optymalizacją odpowiedzi z najbardziej podstawowej implementacji brutalnej siły, którą zrobiłbym z tym zwariowanym krótkim kodem, który widzę, wysyłacie; ale czuję, że każde wyjaśnienie jest o krok bliżej, dziękuję!
Magic Octopus Urn
5

Pyth, 13 12 bajtów

JsM^UQ3s/LJJ

Oszczędność jednego bajtu dzięki Dziurawej Zakonnicy.

Wyjaśnienie

JsM^UQ3s/LJJ
   ^UQ3         Get all triples in the range.
JsM             Save the sums as J.
        /LJJ    Count occurrences of each element of J in J.
       s        Take the sum.

źródło
+1 za niestosowanie formuły bezpośredniej: P.
Magic Octopus Urn
Możesz opublikować link do tłumacza online .
Leaky Nun
Możesz także użyć /LJJzamiast m/JdJ.
Leaky Nun
2

TI-BASIC, 19 bajtów

:Prompt X
:.05X(11X^4+5X²+4

Ocenia formułę OEIS.

Scott Milner
źródło
1
Jak liczycie bajty tutaj? Prompt x= 2 bajty?
Magic Octopus Urn
@carusocomputing TI-BASIC jest punktowany przez żetony
dzaima 28.04.17
1
Trochę smutne, że zamieściłem odpowiedź TI-BASIC 5 razy wcześniej i nigdy nie uzyskałem poprawnej oceny teraz, gdy przeglądam swoją historię ._.
Magic Octopus Urn
2

Oaza , 17 bajtów

5m11*n3m5*nz++20÷

5                   n 5             implicit n for illustration
 m                  n**5
  11                n**5 11
    *               11*n**5
     n              11*n**5 n
      3             11*n**5 n 3
       m            11*n**5 n**3
        5           11*n**5 n**3 5
         *          11*n**5 5*n**3
          n         11*n**5 5*n**3 n
           z        11*n**5 5*n**3 4*n
            +       11*n**5 5*n**3+4*n
             +      11*n**5+5*n**3+4*n
              20    11*n**5+5*n**3+4*n 20
                ÷  (11*n**5+5*n**3+4*n)÷20

Wypróbuj online!

Oasis to język oparty na stosie, zoptymalizowany pod kątem powtarzających się sekwencji. Jednak formuła rekurencji byłaby w tym przypadku zbyt długa.

Leaky Nun
źródło
2

Brachylog , 17 bajtów

{>ℕ|↰}ᶠ⁶ḍD+ᵐ=∧D≜ᶜ

Wypróbuj online!

Wyjaśnienie

{  |↰}ᶠ⁶           Generate a list of 6 variables [A,B,C,D,E,F]...
 >ℕ                  ...which are all in the interval [0, Input)
        ḍD         Dichotomize; D = [[A,B,C],[D,E,F]]
          +ᵐ=      A + B + C must be equal to D + E + F
             ∧
              D≜ᶜ  Count the number of possible ways you can label the elements of D while
                     satisfying the constraints they have
Fatalizować
źródło
Chyba powinienem automatycznie przyjechać
Leaky Nun
@LeakyNun Nie możesz biegać sam, to metapredykat.
Fatalize
Ale mimo to, jeśli zostanie użyty na liście, oznaczenie tej listy może być domyślnym predykatem, prawda?
mat
@mat Można to zrobić w ten sposób, ale w tej chwili nie można używać metapredykatu na zmiennej.
Fatalize
1

JavaScript, 24 bajty

x=>11*x**5/20+x**3/4+x/5

Wykorzystuje formułę ze strony OEIS.

Wypróbuj online!

Fəˈnɛtɪk
źródło
Myślę, że możesz zaoszczędzić dwa bajty za pomocąx=>x**5*.55+x**3/4+x/5
ETHproductions
@ETHproductions występują błędy zmiennoprzecinkowe, jeśli użyję * .55 zamiast *
11/20
1

Oktawa , 25 23 21 bajtów

@(n).55*n^5+n^3/4+n/5

Wypróbuj online!

Wykorzystuje wzór z wpisu OEIS. Zaoszczędzono dwa cztery bajty , zmieniając formułę i używając .55zamiast 11/20, dzięki fəˈnɛtɪk.

Stewie Griffin
źródło
1

Python 2.7, 109 105 99 96 bajtów

Dzięki ETHproductions i Dennis za zaoszczędzenie kilku bajtów:

from itertools import*
lambda s:sum(sum(x[:3])==sum(x[3:])for x in product(range(s),repeat=6))
acidtobi
źródło
Ciekawe, czy Python 3 nie ma funkcji krótszego zasięgu niż 2.7?
Magic Octopus Urn
sum(sum(x[:3])==sum(x[3:])for x ...)byłby jeszcze krótszy. Ponadto from itertools import*oszczędza bajt.
Dennis
Nie potrzebujesz wcześniej miejsca for. Nie wymagamy też domyślnego nadawania nazw funkcjom, aby można je było usunąć h=.
Dennis
1

Mathematica, 52 bajty

Implementacja formuły OEIS przez Kelly Lowder jest znacznie krótsza, ale oblicza to bezpośrednio:

Count[Tr/@#~Partition~3&/@Range@#~Tuples~6,{n_,n_}]&

Cóż, w rzeczywistości liczy się liczba rozwiązań 1 <= a,b,c,x,y,z <= n. Jest to ta sama liczba, ponieważ dodanie 1 do wszystkich zmiennych nie zmienia równości.

Objaśnienie: Range@#~Tuples~6tworzy wszystkie listy sześciu liczb całkowitych od 1 do n, #~Partition~3&/@dzieli każdą listę na dwie listy o długości 3, Tr/@sumuje te listy podrzędne i Count[...,{n_,n_}]liczy, ile par ma taką samą sumę. Miałem dużo szczęścia w kolejności pierwszeństwa między f @, f /@a ~f~!

Nie drzewo
źródło
1

Oktawa , 41 bajtów

@(n)round(max(ifft(fft(~~(1:n),n^2).^6)))

Wypróbuj online!

Podobnie do mojej odpowiedzi MATL , ale oblicza splot za pomocą dyskretnej transformaty Fouriera ( fft) z wystarczającą liczbą punktów ( n^2). ~~(1:n)jest używany jako krótsza wersja ones(1,n). roundjest konieczne z powodu błędów zmiennoprzecinkowych.

Luis Mendo
źródło
0

CJam , 17 bajtów

ri,6m*{3/::+:=},,

Wprowadzanie 11limitów czasu w TIO 12i więcej kończy się pamięć.

Wypróbuj online!

Wyjaśnienie

ri                e# Read an int from input.
  ,               e# Generate the range 0 ... input-1.
   6m*            e# Take the 6th Cartesian power of the range.
      {           e# Keep only the sets of 6 values where:
       3/         e#  The set split into (two) chunks of 3
         ::+:=    e#  Have the sums of both chunks equal.
              },  e# (end of filter)
                , e# Get the length of the resulting list.
Business Cat
źródło
0

Clojure, 79 bajtów

#(count(for[r[(range %)]a r b r c r x r y r z r :when(=(+ a b c)(+ x y z))]1))

Mnóstwo powtórzeń w kodzie, przy większej liczbie zmiennych makro może być krótsze.

NikoNyrh
źródło