Fünfeckige Zahlen aus fünfeckigen Zahlen

15

Einführung

Eine fünfeckige Zahl ( A000326 ) wird durch die Formel P n = 0,5 × (3n 2 -n) erzeugt . Oder Sie können einfach die Anzahl der verwendeten Punkte zählen:

Bildbeschreibung hier eingeben

Sie können die Formel oder das GIF oben verwenden, um die ersten fünfeckigen Zahlen zu finden:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, 176, 210, 247, 287, 330, 376, 425, 477, etc...

Als nächstes müssen wir die Summe von x aufeinanderfolgenden Zahlen berechnen .

Wenn zum Beispiel x = 4 ist , müssen wir P n + P n + 1 + P n + 2 + P n + 3 betrachten (was aus 4 Termen besteht). Wenn die Summe der fünfeckigen Zahlen auch eine fünfeckige Zahl ist, nennen wir dies eine fünfeckige Fünfeckzahl .

Für x = 4 , ist die kleinste pentagonal Fünfeck Zahl 330, die aus gemacht wird 4 aufeinander folgende Fünfeckszahl: 51, 70, 92, 117. Wenn also der Eingang ist 4, sollte Ihr Funktionsprogramm ausgeben 330.


Aufgabe

  • Bei einer Ganzzahl größer als 1 wird die kleinste fünfeckige Fünfeckzahl ausgegeben.
  • Sie können eine Funktion oder ein Programm bereitstellen.
  • Hinweis: Es gibt keine Lösungen für zB x = 3 . Dies bedeutet, dass wenn eine Nummer nicht gemacht werden kann aus den ersten 10000 fünfeckigen Zahlen , müssen Sie die Berechnung beenden und das ausgeben, was am besten zu Ihnen passt.
  • Das ist , also gewinnt die Einsendung mit der geringsten Anzahl von Bytes!

Testfälle:

Input: 2
Output: 1926 (which comes from 925, 1001)

Input: 3
Output: ?

Input: 4
Output: 330 (which comes from 51, 70, 92, 117)

Input: 5
Output: 44290 (which comes from 8400, 8626, 8855, 9087, 9322)

Input: 6
Output: 651 (which comes from 51, 70, 92, 117, 145, 176)

Input: 7
Output: 287 (which comes from 5, 12, 22, 35, 51, 70, 92)

Input: 8
Output: ?

Input: 9
Output: 12105 (which comes from 1001, 1080, 1162, 1247, 1335, 1426, 1520, 1617, 1717)

Input: 10
Output: ?

Es können auch größere Zahlen angegeben werden:

Input: 37
Output: 32782

Input: 55
Output: 71349465

Input: 71
Output: 24565290
Adnan
quelle
4
IMO ist es verrückt, jemanden zu bestrafen, der eine analytische Lösung findet, die die schwierigeren Fälle lösen kann, indem er von ihm verlangt, zu prüfen, ob die Lösung kleiner ist als10001-x
Peter Taylor
1
@PeterTaylor Mit härteren Fällen meinst du gerne x = 3, welche haben keine Lösungen?
Adnan
4
Der größte Testfall, der ein Ergebnis liefert: 9919->496458299155
Martin Ender
Nein, ich meine Fälle, die Lösungen haben, aber in der Summe größere fünfeckige Zahlen verwenden.
Peter Taylor
1
Ich bin mir nicht sicher, ob das Limit von 10.000 gilt: Müssen die Zahlen, die die Summe bilden, aus den ersten 10.000 fünfeckigen Zahlen stammen, nicht aber die Summe selbst, oder muss die Summe auch innerhalb der ersten 10.000 liegen?
Nimi

Antworten:

4

CJam, 29 Bytes

6e5{)_3*(*2/}%_A4#<riew::+&1<

Probieren Sie es online aus.

Die Ausführung dauert einige Sekunden.

Erläuterung

Zuerst müssen wir überprüfen, wie viele Fünfeckzahlen wir als mögliche Summen betrachten müssen. Die Summe der ersten 10.000 Fünfeckzahlen ist 500050000000. Die erste größere fünfeckige Zahl ist die 577.380.

6e5       e# 600,000 (a short number that's a bit bigger than we need).
{         e# Map this block onto every number from 0 to 599,999...
  )       e#   Increment.
  _3*(*2/ e#   Apply the pentagonal number formula given in the challenge.
}%
_         e# Make a copy.
A4#<      e# Truncate to the first 10,000 elements.
ri        e# Read input and convert to integer.
ew        e# Get sublists of that length.
::+       e# Sum each sublist.
&         e# Set intersection with all 600k pentagonal numbers computed earlier.
1<        e# Truncate to the first result.

Ich habe ein leicht modifiziertes Programm verwendet, um die größten Eingaben zu finden, die eine nicht leere Lösung ergeben. Dies sind alle Lösungen für Eingaben über 9.000:

9919 -> 496458299155
9577 -> 446991927537
9499 -> 455533474060
9241 -> 401702906276
9017 -> 429351677617
Martin Ender
quelle
4

Lua, 142 Bytes

p={}o={}n=...for i=1,10^4 do p[i]=(3*i^2-i)/2o[p[i]]=1 end for i=0,10^4-n do s=0 for j=1,n do s=s+p[i+j]end if(o[s])then print(s)break end end

Ungolfed

p={}o={}n=tonumber(...)
for i=1,10^4 do 
    p[i]=(3*i^2-i)/2o[p[i]]=1 
end
for i=0,10^4-n do 
    s=0 
    for j=1,n do 
        s=s+p[i+j]
    end 
    if(o[s])then 
        print(s)
        break 
    end 
end

Yay für das Umkehren von Tabellen!

Update 142 Bytes: Durch Entfernen des überflüssigen Funktionsaufrufs 'tonumber' wurden 10 Bytes gespeichert.

Cyv
quelle
3

Haskell, 109 Bytes

p=map(\n->div(3*n^2-n)2)[1..10^7]
(%)=(sum.).take
x#l|length l<x=0|elem(x%l)p=x%l|1<2=x#tail l
(#take(10^4)p)

Kehrt zurück 0 wenn keine fünfeckige Fünfeckzahl vorhanden ist.

Anwendungsbeispiel (dauert einige Zeit): map (#take(10^4)p) [1..10]->[1,1926,0,330,44290,651,287,0,12105,0] .

Es ist mehr oder weniger eine direkte Implementierung der Definition: Wenn sich die Summe der ersten xElemente in der Liste befindet, geben Sie sie aus, oder wiederholen Sie den Versuch mit dem Ende der Liste. Beginnen Sie mit den ersten 10.000 fünfeckigen Zahlen, halten Sie an und kehren Sie zurück, 0wenn die Liste weniger als xElemente enthält.

nimi
quelle
3

PARI / GP, 71 Bytes

Ich mag die ispolygonalFunktion in PARI / GP.

x->[p|p<-vector(10^4,i,sum(n=i,i+x-1,(3*n^2-n)/2)),ispolygonal(p,5)][1]
Alephalpha
quelle
3

Python 3, 144 Bytes

R,P=range,list(map(lambda n:(3*n*n-n)/2,R(1,10001)))
def F(X):
 for a in R(0,len(P)-X):
    S=sum(P[a:a+X])
    if(1+(1+24*S)**.5)%6==0:print(S);break

Dies kehrt die Definition einer fünfeckigen Zahl um; Wenn P (n) = (3n ^ 2-n) / 2, dann ist ein gegebenes P eine fünfeckige Zahl, wenn f (1 + sqrt (24 * P + 1)) / 6 eine ganze Zahl ist. (Technisch sollte es auch (1-sqrt (24 * P + 1)) / 6 sein, aber das sollte immer negativ sein.) Verwendet auch Leerzeichen und Tabulatoren als zwei verschiedene Einrückungsstufen, wie hier vorgeschlagen . Dies gibt nichts aus, wenn keine fünfeckige fünfeckige Zahl gefunden werden kann. Ich vertraue darauf, dass das in Ordnung ist?

Ich bin der festen Überzeugung, dass jemand, der schlauer ist als ich, einen Weg finden könnte, dies noch weiter zu verkürzen, wahrscheinlich um die for-Schleife herum.

Jack Brounstein
quelle
2

LabVIEW, 39 LabVIEW-Grundelemente

Diesmal läuft kein GIF davon.

Der Math-Knoten in der Schleife erstellt ein Array aller Zahlen. Nehmen Sie ein Sub-Array, fügen Sie Elemente hinzu, suchen Sie nach dieser Nummer, falls gefunden, nehmen Sie einen Index und stoppen Sie die Schleife.

Eine ungültige Eingabe gibt die höchste fünfeckige Zahl aus.

Eumel
quelle
2

R 114 100 Bytes

k=.5*(3*(t=1:1e6)^2-t);z=1;for(i in 1:(1e4-(n=scan()-1)))z[i]=sum(k[i:(i+n)]);cat(intersect(k,z)[1])

ungolfed (irgendwie)

k=.5*(3*(t=1:1e6)^2-t)                 # map all pentagon numbers up to 1e6
z=1                                    # create a vector
for(i in 1:(1e4-(n=scan()-1))){        # from 1 to 10.000 - n loop
  z[i]=sum(k[i:(i+n)])}                # get the sum of all pentagon numbers i:(i+n)
cat(intersect(k,z)[1])                 # see which sums is a pentagon number itself, plot the first
Mutador
quelle
2

Gelee , 30 Bytes

×24‘½‘%6¬Oị
15ȷ7RÇṫ³R$zȷ.5ZSÇḢ

Dieser Code funktioniert mit dieser Version von Jelly und entspricht dem folgenden Binärcode:

0000000: 94 32 34 b2 90 b2 25 36 87 4f b1 0a 31 35 a0  .24...%6.O..15.
000000f: 37 52 92 ad 8b 52 24 7a a0 2e 35 5a 53 92 a6  7R...R$z..5ZS..

Es ist bei weitem langsam und Speicher hungrig für das Online - Interpreter, da es die ersten 150.000.000 für pentagonality prüft (149.995.000 nun mal die 10.000 seine th Fünfeckszahl).

Wenn Sie die Reichweite auf etwas Sinnvolleres verkürzen, können Sie es online ausprobieren! für ausreichend kleine eingänge.

Idee

Ein bekanntes Ergebnis für fünfeckige Zahlen ist x genau dann wenn sqrt (24x + 1) - 1 durch 6 teilbar ist .

Anstatt die ersten 10.000 fünfeckigen Zahlen zu berechnen, definieren wir eine Hilfsverknüpfung, mit der nichtfünfeckige Zahlen aus einem bestimmten Array entfernt werden. Warum? Da die neueste Version von Jelly vor dieser Herausforderung keine Möglichkeit hat, Listen zu schneiden ...

Code

×24‘½‘%6¬Oị  Define the aforementioned helper link. Left argument: a (list)

×24          Multiply each list item by 24.
   ‘         Increment each product.
    ½        Apply square root to each result.
     ’       Decrement each square root.
      %6     Compute all remainders of division by 6.
        ¬    Apply logical NOT.
         O   Get the indices of ones.
          ị  Hook; get the elements of a at those indices.

15ȷ7RÇṫ³R$zȷ.5ZSÇḢ  Define the main link. Input: x

15ȷ7R               Yields [1, ..., 1.5e8].
     Ç              Apply the helper link; keep only pentagonal numbers.
       ³R$          Yield r = [1, ..., x].
      ṫ             Remove the first y-1 pentagonal numbers for each y in r.
          zȷ.5      Transpose the resulting array, padding with sqrt(10).
              Z     Transpose once more. The shifted lists have now been padded.
                    This makes sure incomplete sums (i.e., of less than x
                    pentagonal numbers) will not be integers.
               S    Compute all sums.
                Ç   Apply the helper link once more.
                 Ḣ  Select the first match, if any.

Jelly, 21 Bytes (nicht konkurrierend)

ȷ6Rµ²×3_¹Hµḣȷ4ṡ³ZSf¹Ḣ

Die neueste Version von Jelly verfügt über zwei neue Funktionen (überlappende Slices und Listenfilter / Überschneidungen) und eine Fehlerbehebung, die eine viel geringere Anzahl von Bytes ermöglicht.

Dieser Code funktioniert auf meinem Desktop-Computer einwandfrei, ist aber für das Zeitlimit von TIO ein bisschen zu langsam. Zu es online auszuprobieren! (Für ausreichend kleine Eingaben) müssen wir den Anfangsbereich noch einmal reduzieren.

Wie es funktioniert

ȷ6Rµ²×3_¹Hµḣȷ4ṡ³ZSf¹Ḣ  Input: x

ȷ6R                    Yield [1, ..., 1,000,000].
   µ                   Begin a new, monadic chain.
    ²                  Square each number in the range.
     ×3                Multiply the squares by 3.
       _¹              Subtract the numbers from the range.
         H             Halve each difference.
                       This yields the first 1,000,000 pentagonal numbers.
          µ            Begin a new, monadic chain.
           ḣȷ4         Keep only the first 10,000 pentagonal numbers.
              ṡ³       Yield all overlapping slices of length x.
                ZS     Transpose and sum. This computes the sum of each slice.
                  f¹   Filter; intersect with the long list of pentagonal numbers.
                    Ḣ  Select the first match, if any.
Dennis
quelle
2

Mathematica 85 Bytes

n=577380;Intersection[#(3#-1)/2&/@Range@n,Table[#((#-1)^2+x(3#-4+3x))/2,{x,n}]][[1]]&

Führt eine Schnellsuche bis P 10 4 durch .

martin
quelle
0

Axiom, 157 Bytes

p(n)==(3*n*n-n)quo 2;f(x)==(a:=0;for i in 1..x repeat a:=a+p(i);for j in 1..10000 repeat(p(floor((1+sqrt(1.+24*a))/6)::INT)=a=>return a;a:=a+p(j+x)-p(j));-1)

ungolfed und ergebnisse

h(x:PI):INT==
   a:=0;for i in 1..x repeat a:=a+p(i) -- sum(p(i),i=1..x)
   for j in 1..10000 repeat
      p(floor((1+sqrt(1.+24*a))/6)::INT)=a=>return a
      a:=a+p(j+x)-p(j)
   -1

(5) -> [[i,f(i)] for i in 1..10]
   (5)
   [[1,1], [2,1926], [3,- 1], [4,330], [5,44290], [6,651], [7,287], [8,- 1],
    [9,12105], [10,- 1]]
                                                  Type: List List Integer

Esplenation: Wir können n mit dem Ergebnis "a" finden, siehe unten

a=(3*n^2-n)/2 => 3*n^2-n-2*a=0 => n=floor((1+sqrt(1.+24*a))/6)::INT

[verwende 1 + sqrt (...), weil n> 0]

Dies oben bedeutet, dass, falls vorhanden, keine solche existiert

p(n0)=a 

als

n0=floor((1+sqrt(1.+24*a))/6)::INT

Weiter müssen wir beweisen, dass p (n0) = a ist, um sicher zu sein (weil es nicht immer so ist)

Aber der Haupttrick wäre, die Summe zu machen

a:=sum(p(i),i=1..x) [x elements sum] 

erst am Anfang, und finden Sie die nächsten x Elemente Summe einfach mit

a=a+p(x+1)-p(1)=sum(p(i), i=2..x+1)

und so weiter für die anderen Summen (Verwendung oben in der Aussage a: = a + p (j + x) - p (j)). Dies bedeutet, dass es nicht notwendig ist, eine Zahl x Elementsumme in der Schleife zu verwenden ... ..

RosLuP
quelle
0

Python 2 , 128 124 Bytes

X=input();N=S=0
while all(S-(3*n*n-n)/2for n in range(S)):N+=1;S=sum(3*(n+N)**2-n-N>>1for n in range(X));N<1e4or 0/0
print S

Probieren Sie es online!

Jonathan Frech
quelle
0

Javascript 93 Bytes

p=i=>i>0&&3*i*i-i>>1
f=(x,i=1,t=0)=>i<1e4?(24*(t+=p(i)-p(i-x))+1)**.5%6==5&i>x?t:f(x,i+1,t):0

console.log(f(4))
console.log(f(5))
console.log(f(6))
console.log(f(7))
console.log(f(8))
console.log(f(9919)==496458299155)
console.log(f(9577)==446991927537)
console.log(f(9499)==455533474060)
console.log(f(9241)==401702906276)
console.log(f(9017)==429351677617)
console.log(f(9))
console.log(f(10))

DanielIndie
quelle