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:

Falsy:

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ą!

code-golf math decision-problem number-theory integer code-golf number decision-problem functional-programming code-golf array-manipulation matrix code-golf string classification string code-challenge binary compression decode code-golf string string code-challenge balanced-string encode code-golf number-theory integer base-conversion code-golf math number-theory geometry abstract-algebra code-golf array-manipulation sorting optimization code-golf math geometry image-processing generation code-golf string cops-and-robbers repeated-transformation grammars cops-and-robbers repeated-transformation grammars code-challenge restricted-source tips source-layout javascript code-challenge kolmogorov-complexity restricted-source code-golf combinatorics counting math fastest-code linear-algebra code-golf math permutations matrix linear-algebra code-golf string decision-problem restricted-source code-golf number array-manipulation subsequence code-golf number array-manipulation matrix code-golf brainfuck code-golf color code-golf quine source-layout code-golf subsequence code-golf string ascii-art code-golf string ascii-art alphabet code-golf decision-problem interpreter hexagonal-grid halting-problem code-golf string polynomials calculus code-golf math decision-problem matrix complex-numbers code-golf random code-golf number arithmetic JungHwan Min
źródło

1

Czy mamy wyprowadzać dane zgodne z prawdą i fałszem, czy też dwie zgodne wartości są w porządku?

Wheat Wizard

@WheatWizard dopuszczalne są dwie spójne wartości.

JungHwan Min

Bez względu na to, jak duże obcięcia nakładają się, wynik jest równoważny mniejszemu trójkątowi z mniejszymi obcięciami (jeśli obcięcia mogą mieć długość boku 0).

Asone Tuhid

8

Haskell, 46 45 bajtów

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

Wypróbuj online!

nimi
źródło

7

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!

xnor
źródło

Naprawdę miłe wytłumaczenie!

Amfibologiczny

6

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!

xnor
źródło

Czy w Pythonie rozwiązania rekurencyjne i nierekurencyjne są zwykle ze sobą tak konkurencyjne?

Boboback

@ Boboquack Zwykle rozwiązanie rekurencyjne wygrywa o kilka bajtów ponad range. Tutaj jest blisko, ponieważ b>n+1jest to długa podstawa i 0injest krótka.

xnor

5

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.

Giuseppe
źródło

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

Vlo

@Vlo facepalm Przyzwyczaiłem się korzystać z funkcji wszędzie ...

Giuseppe

I właśnie przyzwyczaiłem się używać <- przypisania zamiast (n = scan ()) ... tsk tsk

Vlo

5

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

Jonathan Allan
źródło

4

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

mudkip201
źródło

Ty też mnie pokonałeś, +1 GG

FantaC

@tfbninja Chciałbym mieć lepsze wyjaśnienie tego, co ɐ-robi

mudkip201

1

dodano, możesz wycofać, jeśli chcesz

FantaC

3

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!

Kreator pszenicy
źródło

Wygląda na to, że czek jest przeoczony a==1.

xnor

@ xnor Rozumiem dlaczego. Zostało to teraz naprawione.

Wheat Wizard

3

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?

kapusta
źródło

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

FrownyFrog

e.2,@(!-/3*!)1+i.,]może

FrownyFrog

3

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

Luis Mendo
źródło

2

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

Asone Tuhid
źródło

2

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!

Dat
źródło

1

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.

Emigna
źródło

1

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

Kudłaty
źródło

1

Dodaj ++ , 36 bajtów

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

Wypróbuj online!

Cairney Coheringaahing
źródło

Czy to jest ścięta liczba trójkątna?

Skrócona liczba trójkątna

Zadanie

Zasady

Przypadki testowe

Odpowiedzi:

Haskell, 46 45 bajtów

Haskell , 46 bajtów

Python 2 , 52 bajty

R , 45 43 bajtów

Galaretka , 10 bajtów

W jaki sposób?

Pyt , 10 bajtów

Haskell , 48 bajtów

J , 22 bajty

Wyjaśnienie

MATL , 12 bajtów

Jak to działa, na przykład

Rubin , 65 57 52 48 bajtów

Python 3 , 84 bajtów

05AB1E , 11 bajtów

Japt , 16 bajtów

Wyjaśnienie

Alternatywny

Dodaj ++ , 36 bajtów