Powiązana sekwencja OEIS: A008867

Skrócona liczba trójkątna

Wspólną właściwością liczb trójkątnych jest to, że można je ułożyć w trójkąt. Na przykład weź 21 i ułóż w trójkąt os:

     o 
    oo
   ooo
  oooo
 ooooo
oooooo

Zdefiniujmy „obcinanie:” wycinanie trójkątów o tym samym rozmiarze z każdego rogu. Jednym ze sposobów obcięcia 21 jest:

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

(Trójkąty .są wycięte z oryginału).

oPozostało 12 s, więc 12 to skrócona liczba trójkątów.

Zadanie

Twoim zadaniem jest napisanie programu lub funkcji (lub odpowiednika), która pobiera liczbę całkowitą i zwraca (lub używa dowolnej standardowej metody wyjściowej), czy liczba jest obciętym numerem trójkąta.

Zasady

• Brak standardowych luk.
• Dane wejściowe to nieujemna liczba całkowita.
• Długość cięcia nie może przekraczać połowy długości oryginalnego trójkąta (tzn. Cięcia nie mogą się pokrywać)
• Cięcie może mieć długość boku zero.

Przypadki testowe

Prawda:

0
1
3
6
7
10
12
15
18
19

Falsy:

2
4
5
8
9
11
13
14
16
17
20

Przypadki testowe dla wszystkich liczb całkowitych do 50: TIO Link

To jest golf golfowy , więc wygrane z najkrótszą liczbą bajtów w każdym języku wygrywają!

Haskell, 46 45 bajtów

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

Wypróbuj online!

Haskell , 46 bajtów

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

Wypróbuj online!

Rzuciłem kilka teorii liczb na problem (dzięki @flawr), znalazłem następującą charakterystykę:

n jest ściętą liczbą trójkątną dokładnie, jeśli w rozkładzie na czynniki pierwsze 4n-1 , dowolna liczba pierwsza w postaci 5 mod 12 lub 7 mod 12 pojawia się parzystą liczbę razy.

Oznacza to na przykład, że 4n-1 może nie być podzielna przez 5, chyba że jest dalej podzielna przez 5 ² = 25, a całkowita liczba 5 czynników jest parzysta.

Haskell nie ma wbudowanej faktoryzacji, ale możemy improwizować. Jeśli pracujemy z rozkładami na czynniki pierwsze, takie jak 12 = 3 * 4 , możemy użyć równoważnego wyrażenia:

n jest ściętą trójkątną liczbą dokładnie, jeśli rozkład na czynniki pierwsze 4n-1 na moc pierwotną nie ma żadnych postaci 5 mod 12 lub 7 mod 12 .

Możemy wyodrębnić moc prime p zawartym w K jak gcd(p^k)k. Następnie sprawdzamy, czy wynik r nie wynosi 5 lub 7 modulo 12 as mod(r-5)12>2. Zauważ, że r jest nieparzyste. Sprawdzamy również kompozyty jako p , nie mogąc odróżnić ich od liczb pierwszych, ale sprawdzenie minie tak długo, jak czynne są jego czynniki.

Wreszcie, negując >2do <3i przełączanie True/ Falsena wyjściu zapisuje bajt pozwalając nam używać orzamiast and.

Pokrewną charakterystyką jest to, że dzielniki 4n-1 wzięte modulo 12 mają więcej całkowitych 1 i 11 niż 5 i 7.

53 bajty

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

Wypróbuj online!

Python 2 , 52 bajty

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

Wypróbuj online!

Wyjścia True/ Falseprzerzucone. Wykorzystuje tę charakterystykę:

n jest liczba ściętego trójkątny dokładnie jeśli 8n-2 ma postać ² -3b ² dla niektórych liczb całkowitych a, b .

Sprawdzamy, czy któryś 8*n-2+3*b*bjest idealnym kwadratem dla każdego bod 1do n+1. Unikamy, b=0ponieważ daje błąd pierwiastka kwadratowego z ujemnego n==0, ale nie może to zaszkodzić, ponieważ tylko dziwne bmoże działać.

Sporządzono nierekurencyjnie:

Python 2 , 53 bajty

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

Wypróbuj online!

R , 45 43 bajtów

-2 bajty dzięki Vlo

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

Wypróbuj online!

Jestem całkiem pewien, że w tym celu musimy sprawdzić tylko pierwsze ntrójkątne liczby; brutalna siła sprawdza, czy nwystępuje w parach różnic liczb trójkątnych i ich potrójnych.

Galaretka , 10 bajtów

0r+\ð_÷3f⁸

Monadyczny link akceptujący liczbę całkowitą i zwracający prawdziwą wartość (niepusta lista) lub wartość falsey (pusta lista).

Wypróbuj online! (stopka wykonuje reprezentację w języku Python, aby pokazać[0]wyniki takimi, jakie są)
... lub zobacz zestaw testów (działa od 0 do 20 włącznie)

W jaki sposób?

Biorąc pod uwagę N, tworzy pierwsze N ​​liczb trójkąta, odejmuje N od każdego z nich, dzieli każdy wynik przez 3 i zachowuje wszelkie wyniki, które są jedną z pierwszych N liczb trójkąta.

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 bajtów

Đř△Đ3*ɐ-Ƒ∈

Wypróbuj online!

Wyjaśnienie:

        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 bajtów

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

Wypróbuj online!

J , 22 bajty

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

Wypróbuj online!

Proste i nieco słabo zagrane golfa podejście.

Wyjaśnienie

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 bajtów

tQ:qYst!3*-m

Wyjścia 1 dla prawdy, 0dla fałszu.

Wypróbuj online!Lub sprawdź wszystkie przypadki testowe .

Jak to działa, na przykład

Rozważ wejście 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

Rubin , 65 57 52 48 bajtów

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

Wypróbuj online!

Zainspirowany pythonową odpowiedzią xnora

Python 3 , 84 bajtów

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]

Wypróbuj online!

05AB1E , 11 bajtów

ÅT3*+8*>ŲZ

Wypróbuj online!

Wyjaśnienie

Å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

Jest to oparte na tym, że liczba T jest trójkątna, jeśli 8T+1jest nieparzystym kwadratem idealnym.
Zaczynamy od listy trójkątów, które moglibyśmy obciąć, obliczyć na ich podstawie możliwe większe trójkąty i sprawdzić, czy w rzeczywistości jest trójkątny.

Japt , 16 bajtów

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

Wypróbuj | Sprawdź wszystkie przypadki testowe

Wyjaśnienie

                     :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

Alternatywny

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

Spróbuj

Dodaj ++ , 36 bajtów

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

Wypróbuj online!