삼각수가 아니야
시퀀스 \$S\$하나의 \$1\$그리고 하나의 \$0\$, 두 개의 \$1\$과 두 \$0\$의 등 :
$$1,0,1,1,0,0,1,1,1,0,0,0,1,1,1,1,0,0,0,0,...$$
(이것은 A118175 : 단일 검정색 셀로 시작하는 Rule 220 기본 셀룰러 오토 마톤의 n 번째 반복의 이진 표현입니다. )
주어진 \$n>0\$, 귀하의 작업은 \$a(n)\$, \ 의 수로 정의$1\$의 중 \$T(n)\$\의 첫 번째 용어$S\$, 여기서 \$T(n)\$는 IS \은$n\$-번째 삼각수 .
처음 몇 가지 용어는 다음과 같습니다.
$$1,2,3,6,9,11,15,21,24,28,36,42,46,55,65,70,78,91,99,105,...$$
그것을 생각하는 한 가지 방법은 \ 의 수를 세는 것입니다.$1\$의 최대 \$n\$\ 의 값으로 채워진 삼각형의-번째 행$S\$:
1 (1)
01 (2)
100 (3)
1110 (6)
00111 (9)
100001 (11)
1111000 (15)
00111111 (21)
000000111 (24)
1111000000 (28)
01111111100 (36)
...
규칙
다음 중 하나를 수행 할 수 있습니다.
- 걸릴 \$n\$입력으로 \$n\$-th term, 1-indexed
- 걸릴 \$n\$입력으로 \$n\$-번째 학기, 0- 색인
- 걸릴 \$n\$입력으로 \$n\$ 첫 학기
- 입력하지 않고 시퀀스를 영원히 인쇄하십시오.
이것은 코드 골프 도전입니다.
답변
젤리 , 9 바이트
ḤR>)FŒHṪS
\를 수락하는 모나 딕 링크$n\$이는 수익률 \$a(n)\$.
온라인으로 시도하십시오! 또는 테스트 스위트를 참조하십시오.
어떻게?
\를 생각할 수 있습니다$S\$길이의 블록으로 만들어지는 것으로 \$2i\$여기서 각 블록은 \ 의 문자열입니다.$i\$뒤에 \$i\$0 : 10 1100 111000 ....
\ 에서 멈 추면$i=x\$결과를 \$S_x\$우리는 \$S_x\$ 반드시 동일한 수의 1과 0을 포함합니다.
우리는 또한 길이 \$S_x\$될 것입니다 \$\sum_{i=1}^{x}2i = 2 \sum_{i=1}^{x}i = 2T(x)\$.
그래서 \$a(x)\$\의 상반기 1의 개수입니다.$S_x\$.
이 같은 결과를 얻는 다른 방법 은 \의 전반부에 있는 0 의 개수를 빼는 것입니다.$S_x\$에서 \$T(x)\$, 그리고 \$S_x\$동일한 수의 1과 0을 포함합니다. 이것은 또한 \의 후반부에있는 0의 개수 여야합니다.$S_x\$. 따라서 우리는 \$S_x\$ 그리고 후반부에있는 것들을 세십시오.
Ḥ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
Wolfram 언어 (Mathematica) , 41 바이트
Sum[1-⌈s=√n⌉+Round@s,{n,#(#+1)/2}]&
온라인으로 시도하십시오!
@ZippyMagician에서 -2 바이트
Husk , 8 바이트
Σ↑ṁṘḋ2NΣ
온라인으로 시도하십시오! 또는 처음 12 개 값 확인
\를 반환합니다.$n^{th}\$ 시퀀스의 값, 1 인덱스.
설명
Σ↑ṁṘḋ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
Python 2 , 47 바이트
f=lambda n,k=8:k>n*-~n*2or(-k**.5%2<1)+f(n,k+4)
온라인으로 시도하십시오!
52 바이트
lambda n:sum(-(k+1)**.5%1<.5for k in range(n*-~n/2))
온라인으로 시도하십시오!
공식에 따라 \$S\$해당 사용자 는 A118175 의 OEIS 페이지에서 기록 됩니다. 0/1에 Booleans를 사용하여 1 인덱싱 된 다음과 같이 단순화합니다.$$ S(k) = \mathrm{frac}(-\sqrt{k}) < \frac{1}{2},$$여기서 \$\mathrm{frac}\$숫자와 바닥의 차이 인 분수 부분을 취합니다. 예 : \$\mathrm{frac}(-2.3)=0.7\$. 이것은 \$\sqrt{k}\$최대 \$\frac{1}{2}\$ 천장보다 낮습니다.
코드는 단순히 합계 $$\sum_{k=1}^{n(n+1)/2} S(k),$$그러나 인수 \$k\$ 인덱스가 0 인 Python 범위를 설명하기 위해 1 씩.
57 바이트
def f(n):N=n*-~n/2;a=round(N**.5);print(a+N-abs(a*a-N))/2
온라인으로 시도하십시오!
플로트를 출력합니다. 직접 산술 공식. Arnauld 덕분에 -1 바이트
Haskell , 48 바이트
f n=sum$sum[1..n]`take`do z<-[1..];[1,0]<*[1..z]
온라인으로 시도하십시오!
Haskell , 48 바이트
sum.(take.sum.r<*>(([1,0]<*).r=<<).r)
r n=[1..n]
온라인으로 시도하십시오!
05AB1E , 12 9 바이트
LxL@˜2äнO
목록 생성에 대한 @JonathanAllan 의 Jelly 답변 에서 영감을 받아 -2 바이트 [1,0,1,1,0,0,1,1,1,0,0,0,...].
출력 \$n^{th}\$값. ( @ovs 에게 감사드립니다 .)
온라인으로 시도 하거나 처음 10 개의 테스트 사례를 확인하십시오 .
대신 무한 시퀀스를 출력하는 10 바이트 버전 :
∞xL@˜∞£OηO
온라인으로 시도하십시오.
설명:
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)
젤리 , 11 바이트
⁵DxⱮRFḣRS$S
온라인으로 시도하십시오!
취하고 \ $ n \는 $ , 출력 \ $ A (N) \ $ 1은 인덱스
작동 원리
⁵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
Charcoal , 24 13 바이트
ＩΣ∕⭆⊕Ｎ⭆10×ιλ²
온라인으로 시도하십시오! 링크는 자세한 코드 버전입니다. 설명:
Ｎ 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
이전 24 바이트의 Charoal-y 솔루션 :
ＮθＧLθψ¤⭆θ⭆²⭆⊕ιλ≔№ＫＡ0θ⎚Ｉθ
온라인으로 시도하십시오! 링크는 자세한 코드 버전입니다. 설명:
Ｎθ
입력 n.
ＧLθψ
side의 빈 직각 삼각형을 그 n립니다.
¤⭆θ⭆²⭆⊕ιλ
문자열을 사용하여 채 웁니다 010011000111.... (문자열은 항상 삼각형의 두 배입니다.) Charcoal의 채우기는 제공된 문자열을 채울 영역에 칠합니다 (예 : Bake a slice of Pi 참조 ). 점을 유의 0s와 1s는 교환된다.
≔№ＫＡ0θ
0실제로 인쇄 된 의 수를 가져옵니다 .
⎚Ｉθ
캔버스를 지우고 결과를 인쇄하십시오.
Python 2 , 62 바이트
a=lambda n,k=1:-~n*n>k*k*2and k+a(n,k+1)or max(0,k-~n*n/2-k*k)
온라인으로 시도하십시오!
이것은
$$ \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} $$
그러나 조건과 기본 케이스는 이것을 단일 재귀 함수로 가져 오기 위해 더 복잡합니다.
K (oK) , 30 25 24 바이트
-coltim 덕분에 6 바이트
{+/(x+/!x)#,/x{0,x,1}\1}
온라인으로 시도하십시오!
인덱싱 된 n 번째 항을 반환합니다.
JavaScript (Node.js) , 100 89 85 84 77 바이트
-11 : 변경 a**2을 a*a단순화 1-Math.ceil(c)+Math.round(c)에 Math.ceil(c)-c<0.5( @xnor )
-4 : c=Math.sqrt(b+1)내부로 이동 Math.ceil(c)하고 f=( @user ) 생략
-1 : ... c<0.5를 ... c<.5( @xnor )로 변경
-7 : 불필요한 (and를 제거 하고 ... 를 ... ( @Samathingamajig )로 )변경합니다 Math.sqrt(.)**.5
a=>(x=0,Array((a*a+a)/2).fill().map((a,b)=>x+=Math.ceil(c=(b+1)**.5)-c<.5),x)
온라인으로 시도하십시오!
APL + WIN, 26 21 바이트.
Adam 덕분에 마이너스 5 바이트.
정수에 대한 프롬프트 :
+/(+/m)↑∊(m←⍳⎕)∘.⍴1 0
온라인으로 시도하십시오! Thamks에서 Dyalog Classic으로
Python 3 , 69 바이트
lambda n:sum([j for i in range(1,n+1)for j in[1]*i+i*[0]][:n*-~n//2])
온라인으로 시도하십시오!
Scala, 66 58 51 바이트
n=>1 to n flatMap(i=>""*i+"\0"*i)take(n*n+n>>1)sum
온라인으로 시도
0x01첫 번째 따옴표 안에 인쇄 할 수없는 문자가 있습니다.
정수를 취하고 n시퀀스의 n 번째 요소 (1 인덱싱 됨)를 반환 하는 익명 함수입니다 .
Haskell , 46 바이트
f n=sum[1|a<-[1..n],b<-[1..a],a*a-b<n*(n+1)/2]
온라인으로 시도하십시오!
46 바이트
f n=sum[max 0$min a$n*(n+1)/2-a*a+a|a<-[1..n]]
온라인으로 시도하십시오!
48 바이트
f n=sum[1|k<-[2,4..n*n+n],even$ceiling$sqrt$2*k]
온라인으로 시도하십시오!
C (gcc) , 84 82 61 바이트
ErikF 덕분에 2 바이트 절약 !
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;}
온라인으로 시도하십시오!
\ 입력$1\$기반 번호 \$n\$그리고 \$n^{\text{th}}\$ 기간.
Haskell , 50 바이트
r?x|q<-sum[0..x]-r*r,r>q=min q 0|l<-r+1=l+l?x
(0?)
온라인으로 시도하십시오!
기존 Haskell 답변과 약간 길지만 완전히 다른 접근 방식입니다. 이것은 기본적으로 모든 산술이지만 기존의 것은 처음부터 목록을 작성합니다.
Retina 0.8.2 , 41 바이트
.+
$* 1 $`1$.`$*00
((.)+?)(?<-2>.)+$ $1
1
온라인으로 시도하십시오! 링크에는 테스트 케이스가 포함됩니다. 설명:
.+
$* 1 $`1$.`$*00
원하는 삼각형의 두 배인 s 및 s 101100111000까지 문자열을 만듭니다 .n 1n 0
((.)+?)(?<-2>.)+$ $1
문자열의 두 번째 절반을 삭제합니다.
1
의 수를 카운트 1나머지들.
J , 25 바이트
(1#.2&!$&;1 0<@#"{~i.)@>:
온라인으로 시도하십시오!
(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
MATL , 15 14 바이트
:"@:t~]vG:s:)z
입력은 1부터 시작합니다.
온라인으로 시도하십시오! 또는 첫 번째 값을 확인하십시오 .
작동 원리
% 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
R , 55 바이트
sum(unlist(Map(rep,list(1:0),e=n<-1:scan()))[1:sum(n)])
온라인으로 시도하십시오!
A118175를 생성하고 첫 번째 \$T(n)\$ 자귀.
Desmos, 85 바이트
\$\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}))
나는 내가 좋은 공식을 찾을 수 없었기 때문에 나는 \$a(n) = 1 - \operatorname{ceil}(\sqrt{n+1}) + \operatorname{round}(\sqrt{n+1})\$A118175의 페이지 에 제공된 공식 .
Gaia , 12 11 10 바이트
┅2…&¦_2÷eΣ
온라인으로 시도하십시오!
에서 관찰 사용 조나단 앨런의 대답 바이트를 저장할을 보완 순서를 구성하고있는 1 초를 계산, 즉 것으로, (그래서 upvote에 이동) 두 번째 절반 것은 상반기에 1 초를 계산하는 것과 동일합니다.
# 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
MathGolf , 19 12 바이트
╒♂░*mzyh½<iΣ
1 기반 \$n^{th}\$ 값.
온라인으로 시도하십시오.
원래 19 바이트 답변 :
╒♂░*mzykæî‼<≥]╡imΣΣ
1 기반 \$n^{th}\$ 가치도 있습니다.
온라인으로 시도하십시오.
설명:
╒ # 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)
Raku , 40 바이트
{sum flat({1,0 Xxx++$}...*)[^sum 1..$_]}
온라인으로 시도하십시오!
{ ... } ... *무한 시퀀스입니다. 여기서 괄호로 묶인 표현식은 각 연속 요소를 생성하는 함수입니다.++$$생성 함수가 평가 될 때마다 익명 상태 변수를 증가시킵니다 . 처음 호출 될 때는++$1, 2 등입니다.1, 0요소가 두 개인 목록입니다.xx복제 연산자입니다. 크로스 제품 metaoperator 접두사X,Xxx리스트 십자가1, 0의 증가 값++$시퀀스를 생성한다(((1), (0)), ((1, 1), (0, 0)), ((1, 1, 1), (0, 0, 0)), ...).flat무한 시퀀스를 주어진 시퀀스 S로 느리게 평평하게1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, ...만듭니다. 즉 : .[^sum 1..$_]해당 시퀀스에서 처음 N 개의 요소를 가져옵니다. 여기서 N은 1$_에서 함수에 대한 인수 까지 숫자의 합입니다 .- 선행
sum은 선택한 요소의 합계입니다.
Arn -rlx , 14 바이트
&♦r┬f½▀╔î¾rl¥Æ
시도 해봐!
설명
포장 풀기 : $.(|{|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
동일한 플래그를 사용하는 대체 14 바이트 솔루션 : $.(a{~:+a@>a}\):_
Arn , 23 바이트
W▀Q$µgˆÎ§Ò"ˆÞC5fbA┐V-7J
시도 해봐! Arn에 라운드 픽스를 추가하는 것을 생각하면이 상당히 많은 바이트 수에 도움이 될 것입니다.
1 인덱싱, N 번째 항을 반환합니다. @ J42161217 의 답변을 기반으로
설명
포장 풀기 : +{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
Swift , 80 바이트
@ovs 의 Python 2 답변에서 수정 됨
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)}
그리고 골프를 치지 않은 형태 :
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)
}
다음은 몇 가지 샘플 출력입니다.
print((1...10).map { a($0) })
// [1, 2, 3, 6, 9, 11, 15, 21, 24, 28]
실제로 재귀 대신 루프를 사용하는 것이 더 나을 수 있습니다. Swift의 클로저 (예 : 람다)에 대한 몇 가지 제한으로 인해 많은 공간을 차지하는 decl 함수를 사용해야했습니다. : /
CJam , 22 바이트
qi),:+{_)mqmo\mqi-}%:+
비트 시퀀스에서 th 위치 round(sqrt(n+1)) - floor(sqrt(n))를 계산하는 데 사용 합니다 n. (숫자의 반복으로 얻는 것은 생성하기에는 더 작았지만 결국 합산하려면 1 바이트 더 컸습니다.)
온라인으로 시도하십시오!
빨간색 , 109 바이트
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]
온라인으로 시도하십시오!
나는 그것이 매우 길다는 것을 알고 있습니다 -K 솔루션 (cortesy @coltim)이 Red에서 어떻게 보이는지보고 싶었습니다. :)