Angka tidak begitu segitiga

Question

Mari kita pertimbangkan urutannya \$S\$terdiri dari satu \$1\$dan satu \$0\$, diikuti oleh dua \$1\$dan dua \$0\$, dan seterusnya:

$$1,0,1,1,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,0,...$$

(Ini adalah A118175 : Representasi biner dari iterasi ke-n dari robot seluler dasar Aturan 220 yang dimulai dengan satu sel hitam. )

Diberikan \$n>0\$, tugas Anda adalah mengeluarkan \$a(n)\$, didefinisikan sebagai jumlah \$1\$di antara \$T(n)\$istilah pertama dari \$S\$, dimana \$T(n)\$adalah \$n\$-bilangan segitiga .

Beberapa istilah pertama adalah:

$$1,2,3,6,9,11,15,21,24,28,36,42,46,55,65,70,78,91,99,105,...$$

Salah satu cara untuk memikirkannya adalah dengan menghitung jumlah \$1\$terserah \$n\$baris ke-3 segitiga yang diisi dengan nilai \$S\$:

1 (1)
01 (2)
100 (3)
1110 (6)
00111 (9)
100001 (11)
1111000 (15)
00111111 (21)
000000111 (24)
1111000000 (28)
01111111100 (36)
...

Aturan

Anda dapat:

• ambil \$n\$sebagai masukan dan kembalikan \$n\$istilah ke-1, 1-indeks
• ambil \$n\$sebagai masukan dan kembalikan \$n\$-th term, 0-indexed
• ambil \$n\$sebagai masukan dan kembalikan \$n\$ istilah pertama
• tidak mengambil masukan dan mencetak urutan selamanya

Ini adalah tantangan kode-golf .

Answer 1

Jeli , 9 byte

ḤR>)FŒHṪS

Tautan monadik menerima \$n\$yang menghasilkan \$a(n)\$.

Cobalah secara online! Atau lihat rangkaian pengujian .

Bagaimana?

Kami dapat memikirkan \$S\$sebagai dibangun dalam balok dengan panjang \$2i\$dimana setiap blok adalah string \$i\$yang diikuti oleh \$i\$nol: 10 1100 111000 ....

Jika kita berhenti di \$i=x\$dan panggil hasilnya \$S_x\$kami tahu itu \$S_x\$ harus berisi angka satu dan nol yang sama.

Kita juga tahu bahwa panjang \$S_x\$akan menjadi \$\sum_{i=1}^{x}2i = 2 \sum_{i=1}^{x}i = 2T(x)\$.

Jadi nilai \$a(x)\$adalah hitungan satu di paruh pertama \$S_x\$.

Cara alternatif untuk mendapatkan hasil yang sama ini adalah dengan mengurangi jumlah nol di paruh pertama \$S_x\$dari \$T(x)\$, dan sejak \$S_x\$berisi jumlah satu dan nol yang sama, ini juga harus menjadi jumlah nol di paruh kedua \$S_x\$. Oleh karena itu kita dapat membentuk komplemen \$S_x\$ dan hitung yang di paruh kedua:

ḤR>)FŒHṪS - Link: integer, n
   )      - for each (i in [1..n]): e.g. i=3
Ḥ         -   double                       6
 R        -   range                        [1,2,3,4,5,6]
  >       -   greater than i?              [0,0,0,1,1,1]
    F     - flatten -> [0,1,0,0,1,1,0,0,0,1,1,1,...]
     ŒH   - split into two equal length parts
       Ṫ  - tail
        S - sum

Answer 2

Bahasa Wolfram (Mathematica) , 41 byte

Sum[1-⌈s=√n⌉+Round@s,{n,#(#+1)/2}]&

Cobalah secara online!

-2 byte dari @ZippyMagician

Answer 3

Husk , 8 byte

Σ↑ṁṘḋ2NΣ

Cobalah secara online! atau Verifikasi 12 nilai pertama

Mengembalikan \$n^{th}\$ nilai urutan, 1 diindeks.

Penjelasan

Σ↑ṁṘḋ2NΣ
  ṁ   N  map the following across natural numbers and concatenate
   Ṙḋ2   replicate [1,0] n times
 ↑       take all values
       Σ till the triangular number of the input
Σ        sum them

Answer 4

Python 2 , 47 byte

f=lambda n,k=8:k>n*-~n*2or(-k**.5%2<1)+f(n,k+4)

Cobalah secara online!

52 byte

lambda n:sum(-(k+1)**.5%1<.5for k in range(n*-~n/2))

Cobalah secara online!

Berdasarkan rumus untuk \$S\$yang pengguna yang dicatat dari halaman Oei dari A118175 . Kami menyederhanakannya menjadi yang berikut, diindeks satu menggunakan Boolean untuk 0/1:$$ S(k) = \mathrm{frac}(-\sqrt{k}) < \frac{1}{2},$$dimana \$\mathrm{frac}\$mengambil bagian pecahan, yaitu selisih antara angka dan lantainya. Misalnya, \$\mathrm{frac}(-2.3)=0.7\$. Ini sama dengan \$\sqrt{k}\$paling banyak \$\frac{1}{2}\$ lebih rendah dari langit-langitnya.

Kode tersebut hanya menjumlahkan $$\sum_{k=1}^{n(n+1)/2} S(k),$$tapi menggeser argumen \$k\$ oleh satu untuk memperhitungkan rentang Python tanpa indeks.

---

57 byte

def f(n):N=n*-~n/2;a=round(N**.5);print(a+N-abs(a*a-N))/2

Cobalah secara online!

Output mengapung. Rumus aritmatika langsung. Terima kasih kepada Arnauld untuk -1 byte

Answer 5

Haskell , 48 byte

f n=sum$sum[1..n]`take`do z<-[1..];[1,0]<*[1..z]

Cobalah secara online!

Haskell , 48 byte

sum.(take.sum.r<*>(([1,0]<*).r=<<).r)
r n=[1..n]

Cobalah secara online!

Answer 6

05AB1E , 12 9 byte

LxL@˜2äнO

-2 byte dengan mengambil inspirasi dari jawaban Jelly @JonathanAllan untuk membuat [1,0,1,1,0,0,1,1,1,0,0,0,...]daftar.

Mengeluarkan \$n^{th}\$nilai. (Terima kasih kepada @ovs .)

Cobalah secara online atau verifikasi 10 kasus pengujian pertama .

Versi 10 byte yang mengeluarkan urutan tak terbatas sebagai gantinya:

∞xL@˜∞£OηO

Cobalah secara online.

Penjelasan:

L           # Push a list in the range [1, (implicit) input]
            #  i.e. input=5 → [1,2,3,4,5]
 x          # Double each value (without popping)
            #  [2,4,6,8,10]
  L         # Convert each value to a [1,n] list as well
            #  [[1,2],[1,2,3,4],[1,2,3,4,5,6],[1,2,3,4,5,6,7,8],[1,2,3,4,5,6,7,8,9,10]]
   @        # Check for each value in the [1,input] list that it's >= the values in the
            # inner ranged lists
            #  [[1,0],[1,1,0,0],[1,1,1,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,0,0,0,0,0]]
    ˜       # Flatten it
            #  [1,0,1,1,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,0]
     2ä     # Split it into 2 equal-sized parts
            #  [[1,0,1,1,0,0,1,1,1,0,0,0,1,1,1],[1,0,0,0,0,1,1,1,1,1,0,0,0,0,0]]
       н    # Only leave the first item
            #  [1,0,1,1,0,0,1,1,1,0,0,0,1,1,1]
        O   # And sum this list
            #  9
            # (after which this sum is output implicitly as result)

∞           # Push an infinite list of positive integers
            #  [1,2,3,...]
 xL@˜       # Same as above
            #  [1,0,1,1,0,0,1,1,1,0,0,0,...]
     ∞      # Push an infinite list again
      £     # Split the list into parts of that size
            #  [[1],[0,1],[1,0,0],[1,1,1,0],...]
       O    # Sum each inner list
            #  [1,1,1,3,...]
        η   # Take the prefixes of that list
            #  [[1],[1,1],[1,1,1],[1,1,1,3],...]
         O  # Sum each inner list
            #  [1,2,3,6,...]
            # (after which the infinite list is output implicitly)

Answer 7

Jeli , 11 byte

⁵DxⱮRFḣRS$S

Cobalah secara online!

Membutuhkan \ $ n \ $ , output \ $ a (n) \ $ , 1-indexed

Bagaimana itu bekerja

⁵DxⱮRFḣRS$S - Main link. Takes n on the left
⁵           - 10
 D          - [1, 0]
    R       - [1, 2, ..., n]
   Ɱ        - For each i in [1, 2, ..., n]:
  x         -   Repeat [1, 0] i times
     F      - Flatten the array
         $  - Group the previous two commands into a monad T(n):
       R    -   [1, 2, ..., n]
        S   -   Sum
      ḣ     - Take the first T(n) elements of the sequence
          S - Take the sum, essentially counting the 1s

Answer 8

Arang , 24 13 byte

ＩΣ∕⭆⊕Ｎ⭆10×ιλ²

Cobalah secara online! Tautan adalah untuk verbose versi kode. Penjelasan:

     Ｎ          Input `n`
   ⭆⊕           Map over inclusive range
      ⭆10       Map over characters of literal string `10`
           λ    Current character
         ×      Repeated by
          ι     Outer index
  ∕         ²   First half of resulting string
 Σ              Digital sum (i.e. count `1`s)
Ｉ               Cast to string
                Implicitly print

Solusi Charoal-y 24-byte sebelumnya:

ＮθＧLθψ¤⭆θ⭆²⭆⊕ιλ≔№ＫＡ0θ⎚Ｉθ

Cobalah secara online! Tautan adalah untuk verbose versi kode. Penjelasan:

Ｎθ

Masukan n.

ＧLθψ

Gambarlah sisi segitiga siku-siku yang kosong n.

¤⭆θ⭆²⭆⊕ιλ

Isi dengan string 010011000111.... (Tali selalu dua kali panjang segitiga.) Pengisian arang mengecat tali yang disediakan ke area yang akan diisi (lihat misalnya Memanggang sepotong Pi ). Perhatikan bahwa 0s dan 1s ditukar.

≔№ＫＡ0θ

Dapatkan jumlah 0yang benar-benar dicetak.

⎚Ｉθ

Kosongkan kanvas dan cetak hasilnya.

Answer 9

Python 2 , 62 byte

a=lambda n,k=1:-~n*n>k*k*2and k+a(n,k+1)or max(0,k-~n*n/2-k*k)

Cobalah secara online!

Ini berdasarkan

$$ \begin{align} a(n) &= f(\frac{n\cdot(n+1)}{2}, 1) \\ \\ f(n, k) &= \begin{cases} k+f(n-2k, k+1), & \text{if $n> k$} \\ \operatorname{max}(0, n), & \text{if $n \ le k$} \end{cases} \end{align} $$

tetapi kondisi dan kasus dasar lebih berbelit-belit untuk membuatnya menjadi fungsi rekursif tunggal.

Answer 10

K (oK) , 30 25 24 byte

-6 byte berkat coltim

{+/(x+/!x)#,/x{0,x,1}\1}

Cobalah secara online!

Mengembalikan indeks ke-1 suku ke-n.

Answer 11

JavaScript (Node.js) , 100 89 85 84 77 byte

-11: Ubah a**2ke a*adan sederhanakan 1-Math.ceil(c)+Math.round(c)menjadi Math.ceil(c)-c<0.5( @xnor )

-4: Pindah ke c=Math.sqrt(b+1)dalam Math.ceil(c)dan hilangkan f=( @user )

-1: Ubah ... c<0.5menjadi ... c<.5( @xnor )

-7: Hapus yang tidak perlu (dan ), dan ubah Math.sqrt(... )menjadi ... **.5( @Samathingamajig )

a=>(x=0,Array((a*a+a)/2).fill().map((a,b)=>x+=Math.ceil(c=(b+1)**.5)-c<.5),x)

Cobalah secara online!

Answer 12

APL + WIN, 26 21 byte.

minus 5 byte berkat Adam.

Perintah untuk integer:

+/(+/m)↑∊(m←⍳⎕)∘.⍴1 0

Cobalah secara online! Thamks ke Dyalog Classic

Answer 13

Python 3 , 69 byte

lambda n:sum([j for i in range(1,n+1)for j in[1]*i+i*[0]][:n*-~n//2])

Cobalah secara online!

Answer 14

Scala, 66 58 51 byte

n=>1 to n flatMap(i=>""*i+"\0"*i)take(n*n+n>>1)sum

Cobalah secara online

Ada karakter yang tidak bisa dicetak 0x01di dalam kutipan pertama.

Fungsi anonim yang mengambil bilangan bulat ndan mengembalikan elemen ke-n dari urutan (diindeks-1).

Answer 15

Haskell , 46 byte

f n=sum[1|a<-[1..n],b<-[1..a],a*a-b<n*(n+1)/2]

Cobalah secara online!

---

46 byte

f n=sum[max 0$min a$n*(n+1)/2-a*a+a|a<-[1..n]]

Cobalah secara online!

---

48 byte

f n=sum[1|k<-[2,4..n*n+n],even$ceiling$sqrt$2*k]

Cobalah secara online!

Answer 16

C (gcc) , 84 82 61 byte

Disimpan 2 byte berkat ErikF !!!

c;p;f(n){for(c=p=0,n=n*-~n/2;n>2*p;n-=2*p++)c+=p;c+=n<p?n:p;}

Cobalah secara online!

Memasukkan \$1\$-berbasis nomor \$n\$dan mengembalikan \$n^{\text{th}}\$ istilah.

Answer 17

Haskell , 50 byte

r?x|q<-sum[0..x]-r*r,r>q=min q 0|l<-r+1=l+l?x
(0?)

Cobalah secara online!

Pendekatan yang sedikit lebih panjang tetapi berbeda dari jawaban Haskell yang ada. Yang ini pada dasarnya semua aritmatika sedangkan yang sudah ada membuat daftar dari awal.

Answer 18

Retina 0.8.2 , 41 byte

.+
$* 1 $`1$.`$*00
((.)+?)(?<-2>.)+$ $1
1

Cobalah secara online! Tautan termasuk kasus uji. Penjelasan:

.+
$* 1 $`1$.`$*00

Buat tali 101100111000... hingga n 1s dan n 0s, yang dua kali panjang segitiga yang diinginkan.

((.)+?)(?<-2>.)+$ $1

Hapus bagian kedua dari string.

1

Hitung jumlah 1s yang tersisa.

Answer 19

J , 25 byte

(1#.2&!$&;1 0<@#"{~i.)@>:

Cobalah secara online!

(1#.2&!$&;1 0<@#"{~i.)@>:
(                    )@>. increment n by 1 and then
                   i.     for every i in 0 … n+1:
          1 0  #"{~         take i 1s and i 0s,
             <@             and box the result (;1 0;1 1 0 0;…)
    2&!                   T(n) by binominal(n+1, 2)
       $&;                raze the boxes to a list (1 0 1 1 0 0…)
                            and take the first T(n) elements
 1#.                      sum the list, i.e. count the 1s

Answer 20

MATL , 15 14 byte

:"@:t~]vG:s:)z

Input berbasis 1.

Cobalah secara online! Atau verifikasi nilai pertama .

Bagaimana itu bekerja

       % Implicit input: n
:      % Range: [1 2 ... n].
"      % For each
  @    %   Push iteration index, k (goes from 1 to n)
  :    %   Range: gives [1 2 ... k]
  t    %   Duplicate
  ~    %   Negate, element-wise: gives [0 0 ... 0] (k zeros)
]      % End
v      % Concatenate everything into a column vector
G      % Push n again
:      % Range: [1 2 ... n]
s      % Sum: gives n-th triangular number, T(n)
:      % Range
)      % Index: keeps the first T(n) values
z      % Number of nonzeros
       % Implicit output

Answer 21

R , 55 byte

sum(unlist(Map(rep,list(1:0),e=n<-1:scan()))[1:sum(n)])

Cobalah secara online!

Menghasilkan A118175 dan menjumlahkan yang pertama \$T(n)\$ istilah.

Answer 22

Desmos, 85 byte

\$\sum_{n=1}^{x(x+1)/2}(1-\operatorname{ceil}(\sqrt{n})+\operatorname{round}(\sqrt{n}))\$

\sum_{n=1}^{x(x+1)/2}(1-\operatorname{ceil}(\sqrt{n})+\operatorname{round}(\sqrt{n}))

Saya sendiri belum dapat menemukan formula yang bagus, jadi saya menggunakan \$a(n) = 1 - \operatorname{ceil}(\sqrt{n+1}) + \operatorname{round}(\sqrt{n+1})\$formula disediakan di halaman A118175 .

Answer 23

Gaia , 12 11 10 byte

┅2…&¦_2÷eΣ

Cobalah secara online!

Menggunakan pengamatan dari jawaban Jonathan Allan untuk menghemat satu byte (jadi naikkan suara itu), yaitu membangun urutan komplemen dan menghitung 1 di paruh kedua sama dengan menghitung 1 di paruh pertama.

		# implicit input n
┅		# push [1, 2, ..., n]
2…		# push [0,1]
&¦		# for each i in [1, 2, ..., n] repeat each element of [0,1] i times
_2÷		# flatten and divide into two sublists of equal length
eΣ		# take the second sublist and sum

Answer 24

MathGolf , 19 12 byte

╒♂░*mzyh½<iΣ

Mengeluarkan \$n^{th}\$ nilai.

Cobalah secara online.

Jawaban asli 19 byte :

╒♂░*mzykæî‼<≥]╡imΣΣ

Mengeluarkan \$n^{th}\$ nilai juga.

Cobalah secara online.

Penjelasan:

╒               # Push a list in the range [1, (implicit) input]
 ♂░             # Push 10, and convert it to a string: "10"
   *            # Repeat the "10" each value amount of times: ["10","1010","101010",...]
    m           # Map over each inner string:
     z          #  Revert sort its digits: ["10","1100","111000",...]
      y         # Join it together to a single string: "101100111000..."
       h        # Push its length (without popping the string itself)
        ½       # Halve it
         <      # Only keep the first length/2 amount of digits in this string
          i     # Convert the string to an integer
           Σ    # And sum its digits
                # (after which the entire stack joined together is output implicitly)

╒♂░*mzy         # Same as above
                # Get its prefixes (unfortunately there isn't a builtin for this):
       k        #  Push the input-integer
        æ       #  Loop that many times,
                #  using the following four characters as body:
         î      #   Push the 1-based loop index
          ‼     #   Apply the following two commands separated:
           <    #    Slice to get the first n items
           ≥    #    Slice to remove the first n items and leave the remainder
        ]       #  After the loop, wrap all values on the stack into a list
         ╡      # Remove the trailing item
          i     # Convert each string of 0s/1s to an integer
           mΣ   # Sum the digits of each inner integer
             Σ  # And sum the entire list together
                # (after which the entire stack joined together is output implicitly)

Answer 25

Raku , 40 byte

{sum flat({1,0 Xxx++$}...*)[^sum 1..$_]}

Cobalah secara online!

• { ... } ... * adalah urutan tak terbatas, di mana ekspresi tanda kurung adalah fungsi yang menghasilkan setiap elemen yang berurutan.
• ++$menambahkan variabel status anonim $setiap kali fungsi penghasil dievaluasi. Pertama kali dipanggil, ++$adalah 1, lalu 2, dll.
• 1, 0 hanyalah daftar dua elemen.
• xxadalah operator replikasi. Diawali dengan metaoperator lintas produk X, Xxxmelintasi daftar 1, 0dengan peningkatan nilai ++$, menghasilkan urutan (((1), (0)), ((1, 1), (0, 0)), ((1, 1, 1), (0, 0, 0)), ...).
• flatmalas merata yang terbatas urutan ke urutan diberikan S, yaitu: 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, ....
• [^sum 1..$_]mengambil N elemen pertama dari urutan itu, di mana N adalah jumlah angka dari 1 hingga $_, argumen ke fungsi.
• Jumlah utama sumelemen yang dipilih.

Answer 26

Arn -rlx , 14 byte

&♦r┬f½▀╔î¾rl¥Æ

Cobalah!

Dijelaskan

Dibongkar: $.(|{|a{a>}\~:+}\

            Mutate STDIN from N → [1, N]
$.                Partition down middle
  (
    |..\            Fold N with concatenation
          _             Where N is a variable; implied
     {                After mapping with block, key of `_`
       |..\
            ~:+             Where N is a one-range to _ * 2
        a{                Block with key of `a`
             a
           >                Is greater than
             _                Implied
        }                 End block
     }                End block   
               Last entry, sum

Alternatif solusi 14 byte dengan flag yang sama: $.(a{~:+a@>a}\):_

Arn , 23 byte

W▀Q$µgˆÎ§Ò"ˆÞC5fbA┐V-7J

Cobalah! Berpikir untuk menambahkan perbaikan putaran ke Arn, itu akan membantu jumlah byte yang cukup tinggi ini.

1-indexed, mengembalikan suku ke-N. Berdasarkan jawaban @ J42161217

Dijelaskan

Dibongkar: +{1-(:^:/)+:v(0.5+:/}\~:-*++

+...\ Fold with addition after mapping
  ~ Over the one-range to
    :-*++ n * (n + 1) / 2
{ Begin map, key of `_`
    1
  - Subtract
    (
      :^ Ceiling
        _ Implied
      :/ Square root
    )
  + Add
    :v(0.5+:/ Round `:/_`, ending implied
} End map

Answer 27

Swift , 80 byte

Diadaptasi dari jawaban Python 2 oleh @ovs

func a(_ n:Int,_ k:Int=1)->Int{-(~n*n)>k*k*2 ? k+a(n,k+1):max(0,k-(~n)*n/2-k*k)}

Dan bentuk tanpa golf:

func a(_ n: Int, _ k: Int = 1) -> Int {
    -(~n*n) > k*k*2
        ? k + a(n, k+1)
        : max(0, k - ~n*n/2 - k*k)
}

Dan inilah beberapa contoh keluarannya.

print((1...10).map { a($0) })
// [1, 2, 3, 6, 9, 11, 15, 21, 24, 28]

Sebenarnya mungkin lebih baik menggunakan loop daripada rekursi. Beberapa batasan dengan closure (mis. Lambda) di Swift memaksa saya untuk menggunakan fungsi yang dideklarasikan, yang memakan banyak ruang. : /

Answer 28

CJam , 22 byte

qi),:+{_)mqmo\mqi-}%:+

Digunakan round(sqrt(n+1)) - floor(sqrt(n))untuk menghitung nposisi ke dalam urutan bit. (Mendapatkan itu sebagai pengulangan angka lebih kecil untuk dihasilkan, tetapi satu byte lebih besar pada akhirnya untuk dijumlahkan.)

Cobalah secara online!

Answer 29

Merah , 109 byte

func[n][b:[[1]]loop n[append/only b head insert next
copy[0 1]last b]sum take/part load form b n + 1 * n / 2]

Cobalah secara online!

Saya tahu ini sangat panjang - saya hanya ingin melihat seperti apa solusi K (cortesy @coltim) di Merah :)