Nomor segitiga terpotong

Properti umum dari bilangan segitiga adalah bahwa angka-angka itu dapat disusun dalam segitiga. Misalnya, ambil 21 dan susun menjadi segitiga os:

     Hai 
    oo
   ooo
  oooo
 ooooo
oooooo

Mari kita mendefinisikan "pemotongan": memotong segitiga dengan ukuran yang sama dari setiap sudut. Salah satu cara untuk memotong 21 adalah sebagai berikut:

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

(Segitiga .dipotong dari aslinya).

Ada 12 odetik yang tersisa, jadi 12 adalah angka segitiga terpotong.

Tugas

Tugas Anda adalah menulis program atau fungsi (atau yang setara) yang mengambil bilangan bulat dan mengembalikan (atau menggunakan salah satu metode output standar) apakah suatu bilangan adalah bilangan segitiga terpotong.

Aturan

Tidak ada celah standar.
Inputnya adalah bilangan bulat non-negatif.
Potongan tidak boleh memiliki panjang sisi melebihi setengah dari segitiga asli (yaitu potongan tidak bisa tumpang tindih)
Potongan dapat memiliki panjang sisi nol.

Uji kasus

Benar:

Falsy:

Kasing uji untuk semua bilangan bulat hingga 50: TIO Link

Ini adalah kode-golf , jadi pengiriman dengan jumlah byte terpendek di setiap bahasa akan menang!

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
sumber

1

Apakah kita akan menampilkan output yang benar dan salah atau dua nilai yang konsisten ok?

Wheat Wizard

@WheatWizard dua nilai konsisten dapat diterima.

JungHwan Min

Betapapun pemotongannya tumpang tindih, hasilnya setara dengan segitiga yang lebih kecil dengan pemotongan yang lebih kecil (jika pemotongan dapat memiliki panjang sisi 0).

Asone Tuhid

8

Haskell, 46 45 byte

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

Cobalah online!

nimi
sumber

7

Haskell , 46 byte

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

Cobalah online!

Setelah melemparkan banyak teori bilangan pada masalah (terima kasih @ flawr), saya menemukan karakterisasi ini:

n adalah bilangan segitiga terpotong persis jika dalam faktorisasi prima dari 4n-1 , bilangan prima apa pun dari bentuk 5 mod 12 atau 7 mod 12 muncul bilangan genap.

Ini berarti, misalnya, bahwa 4n-1 mungkin tidak dapat dibagi dengan 5 kecuali jika selanjutnya dapat dibagi dengan 5 ² = 25 dan jumlah total 5 faktor adalah genap.

Haskell tidak memiliki faktorisasi bawaan, tetapi kita dapat berimprovisasi. Jika kita bekerja dengan faktorisasi ke dalam bilangan prima seperti 12 = 3 * 4 , kita dapat menggunakan pernyataan yang setara:

n adalah bilangan segitiga terpotong tepat jika faktorisasi 4n-1 menjadi kekuatan utama tidak memiliki syarat bentuk 5 mod 12 atau 7 mod 12 .

Kita dapat mengekstrak kekuatan p prima yang muncul dalam k sebagai gcd(p^k)k. Kami kemudian memeriksa bahwa hasilnya r bukan 5 atau 7 modulo 12 sebagai mod(r-5)12>2. Perhatikan bahwa r aneh. Kami juga memeriksa komposit sebagai p , tidak memiliki cara untuk memberi tahu mereka dari bilangan prima, tetapi pemeriksaan akan berlalu selama faktor-faktornya.

Akhirnya, meniadakan >2ke <3dan beralih True/ Falsedalam output menghemat satu byte dengan membiarkan kami menggunakan orbukan and.

Karakterisasi terkait adalah bahwa pembagi 4n-1 yang diambil modulo 12 memiliki total lebih banyak 1 dan 11 dari 5 dan 7.

53 byte

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

Cobalah online!

Tidak
sumber

Penjelasan yang sangat bagus!

Amfibologis

6

Python 2 , 52 byte

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

Cobalah online!

Output True/ Falseterbalik. Gunakan karakterisasi ini:

n adalah dipotong sejumlah segitiga persis jika 8N-2 memiliki membentuk sebuah ² -3b ² untuk beberapa bilangan bulat a, b .

Kami memeriksa apakah ada yang 8*n-2+3*b*bmerupakan kuadrat sempurna untuk siapa pun bdari 1hingga n+1. Kami menghindarinya b=0karena memberikan kesalahan untuk akar kuadrat dari waktu negatif n==0, tetapi ini tidak ada salahnya karena hanya aneh yang bbisa bekerja.

Dilakukan secara non-rekursif:

Python 2 , 53 byte

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

Cobalah online!

Tidak
sumber

Apakah solusi rekursif dan non-rekursif biasanya saling bersaing dengan python?

boboquack

@ Boboquack Biasanya solusi rekursif menang beberapa byte lebih range. Ini dia dekat karena b>n+1alasnya panjang dan 0inpendek.

xnor

5

R , 45 43 byte

-2 byte terima kasih kepada Vlo

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

Cobalah online!

Saya cukup yakin kita hanya perlu memeriksa nangka segitiga pertama untuk ini; brute force memeriksa apakah nada perbedaan berpasangan dari angka segitiga dan tiga kali lipatnya.

Giuseppe
sumber

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

Vlo

@Vlo facepalm saya terbiasa menggunakan fungsi di mana-mana ...

Giuseppe

Dan saya baru saja terbiasa menggunakan <- tugas alih-alih (n = scan ()) ... tsk tsk

Vlo

5

Jelly , 10 byte

0r+\ð_÷3f⁸

Tautan monadik yang menerima bilangan bulat dan mengembalikan nilai kebenaran (daftar yang tidak kosong) atau nilai falsey (daftar kosong).

Cobalah online! (footer melakukan representasi Python untuk menunjukkan[0]hasilnya apa adanya)
... atau melihat test-suite (berlaku untuk 0 hingga 20 inklusif)

Bagaimana?

Diberikan N, bentuk angka segitiga N pertama, kurangi N dari masing-masing, bagi setiap hasil dengan 3 dan simpan hasil apa pun yang merupakan salah satu dari angka segitiga N pertama.

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
sumber

4

Pyt , 10 byte

Đř△Đ3*ɐ-Ƒ∈

Cobalah online!

Penjelasan:

        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
sumber

Anda juga mengalahkan saya, +1 GG

FantaC

@tfbninja Saya berharap saya memiliki penjelasan yang lebih bagus untuk apa yang ɐ-dilakukannya

mudkip201

1

menambahkan, Anda dapat

mengembalikan

3

Haskell , 48 byte

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

Cobalah online!

Wisaya Gandum
sumber

Sepertinya cek Anda menghadap a==1.

xnor

@ xnor Saya mengerti mengapa. Sudah diperbaiki sekarang.

Wheat Wizard

3

J , 22 byte

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

Cobalah online!

Pendekatan langsung dan agak buruk golf.

Penjelasan

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?

cole
sumber

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

FrownyFrog

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

FrownyFrog

3

MATL , 12 byte

tQ:qYst!3*-m

Keluaran 1untuk kebenaran, 0untuk kepalsuan.

Cobalah online! Atau verifikasi semua kasus uji .

Cara kerjanya, misalnya

Pertimbangkan input 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
sumber

2

Ruby , 65 57 52 48 byte

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

Cobalah online!

Terinspirasi oleh jawaban python xnor

Asone Tuhid
sumber

2

Python 3 , 84 byte

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]

Cobalah online!

Dat
sumber

1

05AB1E , 11 byte

ÅT3*+8*>Å²Z

Cobalah online!

Penjelasan

Å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

Ini didasarkan pada fakta bahwa bilangan T berbentuk segitiga jika 8T+1kuadrat sempurna ganjil.
Kita mulai pada daftar segitiga yang dapat kita potong, hitung kemungkinan segitiga yang lebih besar berdasarkan padanya dan periksa apakah itu sebenarnya segitiga.

Emigna
sumber

1

Japt , 16 byte

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

Cobalah | Periksa semua test case

Penjelasan

                     :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

Alternatif

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

Cobalah

Shaggy
sumber

1

Tambahkan ++ , 36 byte

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

Cobalah online!

caird coinheringaahing
sumber

Apakah ini bilangan segitiga terpotong?

Nomor segitiga terpotong

Tugas

Aturan

Uji kasus

Jawaban:

Haskell, 46 45 byte

Haskell , 46 byte

Python 2 , 52 byte

R , 45 43 byte

Jelly , 10 byte

Bagaimana?

Pyt , 10 byte

Haskell , 48 byte

J , 22 byte

Penjelasan

MATL , 12 byte

Cara kerjanya, misalnya

Ruby , 65 57 52 48 byte

Python 3 , 84 byte

05AB1E , 11 byte

Japt , 16 byte

Penjelasan

Alternatif

Tambahkan ++ , 36 byte