Sammlung aus einer Sequenz, die ein perfektes Quadrat darstellt

10

In Anbetracht der Folge OEIS A033581 , die die unendliche Folge ist, ist der n -te Term (0-Indexierung) durch die geschlossene Formformel 6 × n 2 gegeben .

Ihre Aufgabe ist es, Code zu schreiben, der alle Teilmengen der Menge von N ersten Zahlen in der Sequenz ausgibt, so dass die Summe der Teilmenge ein perfektes Quadrat ist.

Regeln

  • Die Ganzzahl Nwird als Eingabe angegeben.
  • Sie können eine bereits in der Summe verwendete Zahl nicht wiederverwenden. (Das heißt, jede Zahl kann höchstens einmal in jeder Teilmenge vorkommen.)
  • Die verwendeten Nummern können nicht aufeinanderfolgend sein.
  • Code mit der geringsten Größe gewinnt.

Beispiel

Die angegebene Sequenz ist {0,6,24,54,96, ..., 15000}

Eine der erforderlichen Teilmengen ist {6,24,294}, weil

6+24+294 = 324 = 18^2

Sie müssen alle diese Sätze aller möglichen Längen im angegebenen Bereich finden.

prog_SAHIL
quelle
3
Guter erster Beitrag! Sie können Beispiele und Testfälle hinzufügen. Zum späteren Nachschlagen haben wir eine Sandbox , in der Sie Ihre Ideen
testen
Bittet uns dies, A033581 mit N zu berechnen? Oder verstehe ich das nicht richtig?
ATaco
@ATaco Wie für eine Sequenz (1,9,35,39 ...) 1 + 9 + 39 = 49 ein perfektes Quadrat (es werden 3 Zahlen verwendet), 35 + 1 = 36 ein weiteres perfektes Quadrat, aber es werden 2 Zahlen verwendet. Also ist {1,35} die erforderliche Menge.
prog_SAHIL
3
@prog_SAHIL Das und ein paar mehr als Beispiele zum Beitrag
hinzuzufügen
Lassen Sie uns diese Diskussion im Chat fortsetzen .
prog_SAHIL

Antworten:

3

05AB1E , 10 Bytes

ݨn6*æʒOŲ

Probieren Sie es online aus!

Wie?

ݨn6 * æʒOŲ || Volles Programm. Ich werde den Eingang N nennen.

Ý || 0-basierter Inklusivbereich. Drücken Sie [0, N] ∩ ℤ.
 ¨ || Entfernen Sie das letzte Element.
  n || Quadrat (elementweise).
   6 * || Mit 6 multiplizieren.
     æ || Powerset.
      ʒ || Filter-Keep diejenigen, die die folgenden erfüllen:
       O || --- | Ihre Summe ...
        Ų || --- | ... ist ein perfektes Quadrat?
Mr. Xcoder
quelle
3

Haskell , 114 104 103 86 Bytes

f n=[x|x<-concat<$>mapM(\x->[[],[x*x*6]])[0..n-1],sum x==[y^2|y<-[0..],y^2>=sum x]!!0]

Vielen Dank an Laikoni und Ørjan Johansen für den größten Teil des Golfspiels! :) :)

Probieren Sie es online aus!

Die etwas besser lesbare Version:

--  OEIS A033581
ns=map((*6).(^2))[0..]

-- returns all subsets of a list (including the empty subset)
subsets :: [a] -> [[a]]
subsets[]=[[]]
subsets(x:y)=subsets y++map(x:)(subsets y)

-- returns True if the element is present in a sorted list
t#(x:xs)|t>x=t#xs|1<2=t==x

-- the function that returns the square subsets
f :: Int -> [[Int]]
f n = filter (\l->sum l#(map(^2)[0..])) $ subsets (take n ns)
Cristian Lupascu
quelle
@ Laikoni Das ist sehr genial! Vielen Dank!
Cristian Lupascu
@ Laikoni Richtig! Vielen Dank!
Cristian Lupascu
86 Bytes: Probieren Sie es online aus!
Ørjan Johansen
2

Pyth , 12 Bytes

-2 Bytes dank Mr. Xcoder

fsI@sT2ym*6*

Probieren Sie es online aus!

2 weitere Bytes müssen hinzugefügt werden, um []und zu entfernen [0], aber sie scheinen mir eine gültige Ausgabe zu sein!


Erklärung

    fsI@sT2ym*6*
    f                  filter
           y           the listified powerset of
            m*6*ddQ    the listified sequence {0,6,24,...,$input-th result}
        sT             where the sum of the sub-list
     sI@  2            is invariant over int parsing after square rooting
Dave
quelle
12 Bytes : fsI@sT2ym*6*.
Mr. Xcoder
Das ist der Platz, auf dem ich nach Golf gesucht habe!
Dave
2

Sauber , 145 ... 97 Bytes

import StdEnv
@n=[[]:[[6*i^2:b]\\i<-[0..n-1],b<- @i]]
f=filter((\e=or[i^2==e\\i<-[0..e]])o sum)o@

Probieren Sie es online aus!

Verwendet die Hilfsfunktion @, um die auf nTerme festgelegte Leistung zu erzeugen, indem jeder Term von [[],[6*n^2],...]mit jedem Term von [[],[6*(n-1)*2],...]rekursiv und in umgekehrter Reihenfolge verkettet wird.

Die Teilfunktion fsetzt sich dann zusammen (wobei Zusammensetzung ->bezeichnet wird o) als:
apply @ -> take the elements where -> the sum -> is a square

Leider ist es nicht möglich, das Literal zu überspringen f=und ein Teilfunktionsliteral bereitzustellen , da Prioritätsregeln erfordern, dass es bei Inline-Verwendung Klammern enthält.

Οurous
quelle
1
Bah du hast einen Trick, den die Haskell-Antwort stehlen sollte ...: P
Ørjan Johansen
1

JavaScript (ES7), 107 Byte

n=>[...Array(n)].reduce((a,_,x)=>[...a,...a.map(y=>[6*x*x,...y])],[[]]).filter(a=>eval(a.join`+`)**.5%1==0)

Demo

Kommentiert

n =>                      // n = input
  [...Array(n)]           // generate a n-entry array
  .reduce((a, _, x) =>    // for each entry at index x:
    [                     //   update the main array a[] by:
      ...a,               //     concatenating the previous values with
      ...a.map(           //     new values built from the original ones
        y =>              //     where in each subarray y:
          [ 6 * x * x,    //       we insert a new element 6x² before
            ...y       ]  //       the original elements
      )                   //     end of map()
    ],                    //   end of array update
    [[]]                  //   start with an array containing an empty array
  )                       // end of reduce()
  .filter(a =>            // filter the results by keeping only elements for which:
    eval(a.join`+`) ** .5 //   the square root of the sum
    % 1 == 0              //   gives an integer
  )                       // end of filter()
Arnauld
quelle
0

Japt , 15 Bytes

ò_²*6Ãà k_x ¬u1

Versuch es


Erläuterung

Generieren Sie ein Array von Ganzzahlen von 0 bis input ( ò) und durchlaufen Sie jeweils eine Funktion ( _ Ã), quadrieren Sie sie ( ²) und multiplizieren Sie sie mit 6 ( *6). Holen Sie sich alle Kombinationen dieses Arrays ( à) und entfernen Sie diejenigen, die truey ( k) zurückgeben, wenn sie eine Funktion ( _) durchlaufen , die ihre Elemente hinzufügt ( x), die Quadratwurzel des Ergebnisses ( ¬) erhält und diese um 1 ( u1) modifiziert.

Zottelig
quelle