Verwandte OEIS-Sequenz: A008867

Abgeschnittene Dreieckszahl

Eine gemeinsame Eigenschaft von Dreieckszahlen ist, dass sie in einem Dreieck angeordnet werden können. Nehmen Sie zum Beispiel 21 und ordnen Sie sie in einem Dreieck aus os an:

     O 
    oo
   ooo
  oooo
 ooooo
oooooo

Definieren wir eine "Kürzung", die aus jeder Ecke gleich große Dreiecke schneidet. Eine Möglichkeit, 21 abzuschneiden, ist wie folgt:

     . 
    . .
   ooo
  oooo
 . ooo.
. . oo. .

(Die Dreiecke von .sind aus dem Original geschnitten).

Es overbleiben 12 Sekunden, sodass 12 eine abgeschnittene Dreieckszahl ist.

Aufgabe

Ihre Aufgabe ist es, ein Programm oder eine Funktion (oder eine Entsprechung) zu schreiben, die eine Ganzzahl annimmt und zurückgibt (oder eine der Standardausgabemethoden verwendet), ob eine Zahl eine abgeschnittene Dreieckszahl ist.

Regeln

• Keine Standardlücken.
• Die Eingabe ist eine nicht negative Ganzzahl.
• Ein Schnitt darf nicht länger als die Hälfte des ursprünglichen Dreiecks sein (dh Schnitte dürfen sich nicht überlappen).
• Ein Schnitt kann eine Seitenlänge von Null haben.

Testfälle

Wahrheit:

0
1
3
6
7
10
12
15
18
19

Falsch:

2
4
5
8
9
11
13
14
16
17
20

Testfälle für alle ganzen Zahlen bis 50: TIO Link

Dies ist Code-Golf , also gewinnen Einsendungen mit kürzesten Bytezahlen in jeder Sprache!

Haskell, 46 45 Bytes

f n|t<-scanl(+)0[1..n]=or[x-3*y==n|x<-t,y<-t]

Probieren Sie es online!

Haskell , 46 Bytes

f n=or[mod(gcd(p^n)(4*n-1)-5)12<3|p<-[1..4*n]]

Probieren Sie es online!

Nachdem ich eine Menge Zahlentheorie auf das Problem geworfen hatte (danke @flawr), fand ich diese Charakterisierung:

n ist eine abgeschnittene Dreieckszahl, genau wenn in der Primfaktorisierung von 4n-1 jede Primzahl der Form 5 mod 12 oder 7 mod 12 eine gerade Anzahl von Malen erscheint.

Dies bedeutet zum Beispiel, dass 4n-1 möglicherweise nicht durch 5 teilbar ist, es sei denn, es ist weiter durch 5 ² = 25 teilbar und die Gesamtzahl der 5 Faktoren ist gerade.

Haskell hat keine eingebaute Faktorisierung, aber wir können improvisieren. Wenn wir mit Faktorisierungen in Primzahlen wie 12 = 3 * 4 arbeiten , können wir die äquivalente Aussage verwenden:

n ist genau dann eine abgeschnittene Dreieckszahl, wenn die Faktorisierung von 4n-1 in Primzahlen keine Terme der Form 5 mod 12 oder 7 mod 12 hat .

Wir können die Potenz eines Prims p extrahieren, der in k as vorkommt gcd(p^k)k. Wir überprüfen dann, dass das Ergebnis r nicht 5 oder 7 modulo 12 as ist mod(r-5)12>2. Beachten Sie, dass r ungerade ist. Wir überprüfen auch Composites als p , da es keine Möglichkeit gibt, sie von Primzahlen zu unterscheiden, aber die Überprüfung wird so lange bestehen, wie es die Faktoren tun.

Schließlich negiert >2zu <3und Schalt True/ Falsespart in der Ausgabe ein Byte , indem Sie uns verwenden orstatt and.

Eine verwandte Charakterisierung ist, dass die Teiler von 4n-1 Modulo 12 mehr Einsen und Elfen als Fünfsen und Siebenen haben.

53 Bytes

f n=sum[abs(mod k 12-6)-3|k<-[1..4*n],mod(4*n)k==1]<0

Probieren Sie es online!

Python 2 , 52 Bytes

f=lambda n,b=1:b>n+1or(8*n-2+3*b*b)**.5%1>0<f(n,b+1)

Probieren Sie es online!

Ausgänge True/ Falseumgedreht. Verwendet diese Charakterisierung:

n ist eine abgeschnittene Dreieckszahl, genau dann, wenn 8n- ² für einige ganze Zahlen a, b die Form a ² -3b ^{2 hat} .

Wir prüfen, ob eines 8*n-2+3*b*bein perfektes Quadrat für eines bvon 1bis ist n+1. Wir vermeiden es, b=0weil es einen Fehler für eine Quadratwurzel eines Negativs gibt n==0, aber das kann nicht schaden, weil nur ungerade bfunktionieren können.

Nicht rekursiv erledigt:

Python 2 , 53 Bytes

lambda n:0in[(8*n-2+3*b*b)**.5%1for b in range(~n,0)]

Probieren Sie es online!

R , 45 43 Bytes

-2 Bytes dank Vlo

(n=scan())%in%outer(T<-cumsum(0:n),3*T,"-")

Probieren Sie es online!

Ich bin mir ziemlich sicher, dass wir dafür nur die ersten nDreieckszahlen überprüfen müssen . Brute Force prüft, ob nes sich bei den paarweisen Differenzen um die Dreieckszahlen und deren Tripel handelt.

Gelee , 10 Bytes

0r+\ð_÷3f⁸

Eine monadische Verknüpfung, die eine Ganzzahl akzeptiert und einen Wahrheitswert (eine nicht leere Liste) oder einen Falsey-Wert (eine leere Liste) zurückgibt.

Probieren Sie es online! (footer führt eine Python-Darstellung durch, um die[0]Ergebnisse so anzuzeigen, wie sie sind)
... oder zeigt eine Testsuite (läuft von 0 bis einschließlich 20)

Wie?

Gegeben N, bildet die ersten N Dreieckszahlen, subtrahiert N von jeder Zahl, dividiert jedes Ergebnis durch 3 und behält alle Ergebnisse bei, die eine der ersten N Dreieckszahlen sind.

0r+\ð_÷3f⁸ - Link: integer, N             e.g. 7
0r         - zero inclusive range N            [    0, 1, 2,   3,    4, 5,   6,   7]
  +\       - cumulative reduce with addition   [    0, 1, 3,   6,   10,15,  21,  28]
    ð      - start a new dyadic link with that, t, on the left and N on the right
     _     - t subtract N (vectorises)         [   -7,-6,-3,  -1,    3, 8,  14,  21]
      ÷3   - divivde by three (vectorises)     [-2.33,-2,-1.33,-0.33,1,2.67,4.67, 7]
         ⁸ - chain's left argument, t          [    0, 1, 3,   6,   10,15,  21,  28]
        f  - filter keep                       [                     1             ]
                                               - a non-empty list, so truthy

Pyt , 10 Bytes

Đř△Đ3*ɐ-Ƒ∈

Probieren Sie es online!

Erläuterung:

        Implicit input
Đ       Duplicate input
ř       Push [1,2,...,input]
△       For each element k in the array, get the kth triangle number
Đ       Duplicate the top of the stack
3*      Multiply by 3
ɐ       ɐ - All possible:
 -                       subtractions between elements of the two arrays  
Ƒ       Flatten the nested array
∈       Is the input in the array

Haskell , 48 Bytes

f a|u<-[0..a]=or[x^2+x-3*(y^2+y)==2*a|x<-u,y<-u]

Probieren Sie es online!

J , 22 Bytes

e.[:,@(-/3*])2![:i.2+]

Probieren Sie es online!

Unkomplizierter und etwas mangelhafter Ansatz.

Erläuterung

e.[:,@(-/3*])2![:i.2+]
             2![:i.2+]  Range of triangular numbers up to N
      (-/3*])           All possible subtractions of 3T from T 
                        where T is triangular up to the Nth triangular number
    ,@                  Flattened into a single list
e.                      Is N in the list?

MATL , 12 Bytes

tQ:qYst!3*-m

Ausgänge 1für Wahres, 0für Falsches.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Wie es funktioniert, mit Beispiel

Betrachten Sie die Eingabe 6

t      % Implicit input. Duplicate
       % STACK: 6, 6
Q:q    % Increase, range, decrease element-wise. Gives [0 1 ... n]
       % STACK: 6, [0 1 ... 6]
Ys     % Cumulative sum
       % STACK: 6, [0 1 3 6 10 15]
t!     % Duplicate, transpose
       % STACK: 6, [0 1 3 6 10 15], [0;
                                     1;
                                     3;
                                     6;
                                     10;
                                     15]
3*     % Times 3, element-wise
       % STACK: 6, [0 1 3 6 10 15 21 28 36 45 55], [0;
                                                    3;
                                                    9;
                                                    18;
                                                    30;
                                                    45]
-      % Subtract, element-wise with broadcast
       % STACK: 6, [  0   1   3   6  10  15  21;
                     -3  -2   0   3   7  12  18;
                     -9  -8  -6  -3   1   6  12;
                    -18 -17 -15 -12  -8  -3   3;
                    -30 -29 -27 -24 -20 -15  -9;
                    -45 -44 -42 -39 -35 -30 -24;
                     -63 -62 -60 -57 -53 -48 -42]
m      % Ismember. Implicit display
       % STACK: 1

Ruby , 65 57 52 48 Bytes

->n,b=0{b+=1;(8*n-2+3*b*b)**0.5%1==0||b<n&&redo}

Probieren Sie es online!

Inspiriert von der Python-Antwort von xnor

Python 3 , 84 Bytes

lambda n:1in set([((8*(n+(i*(i+1)/2)*3)+1)**0.5)%4==1for i in range(n)])or n in[0,1]

Probieren Sie es online!

05AB1E , 11 Bytes

ÅT3*+8*>ŲZ

Probieren Sie es online!

Erläuterung

ÅT            # get a list of triangle numbers upto input
  3*          # multiply each by 3
    +         # add input to each
     8*       # multiply each by 8
       >      # increment each
        Ų    # check each for squareness
          Z   # max

Dies beruht auf der Tatsache, dass eine Zahl T dreieckig ist, wenn 8T+1es sich um ein ungerades perfektes Quadrat handelt.
Wir beginnen mit der Liste der Dreiecke, die wir abschneiden könnten, berechnen die möglichen größeren Dreiecke basierend auf diesen und prüfen, ob sie tatsächlich dreieckig sind.

Japt , 16 Bytes

ò å+ d@Zd_-3*X¶U

Versuchen Sie es | Überprüfen Sie alle Testfälle

Erläuterung

                     :Implicit input of integer U
ò                    :Range [0,U]
  å+                 :Cumulative reduction by addition
     d@              :Does any X in array Z return true when passed through this function?
       Zd_           :  Does any element in Z return true when passe through this function?
          -3*X       :    Subtract 3*X
              ¶U     :    Check for equality with U

Alternative

ò å+ £Zm-3*XÃdøU

Versuch es

Add ++ , 36 Bytes

D,g,@,.5^di=
L,ßR¬+A↑>3€*A€+8€*1€+ºg

Probieren Sie es online!