모든 수학 중에서 항상 상식을 넘어서는 몇 가지 이론이 있습니다. 이것들 중 하나는 서로 다른 크기의 무한대가 있다는 사실입니다. 또 다른 흥미로운 사실은 크기가 다른 것처럼 보이는 많은 무한대가 실제로 같은 크기라는 생각입니다. 유리수만큼 정수만큼의 짝수도 있습니다.

이 질문의 일반적인 개념은 기괴한 무한대의 현실과 대면하는 것입니다. 이 과제에서 프로그램은 다음과 같은 목록을 출력합니다.

• 특정 시점에 항상 전체 항목 수를 갖습니다.
• 결국 전체 목록에서 특정 (0이 아닌) 합리적인 숫자를 정확히 한 번만 포함하십시오 (충분히 오래 방치하면).
• 무제한의 빈 슬롯을 포함합니다 (필수없이 0으로 설정된 목록의 항목).
• 빈 슬롯의 비율이 100 %로 제한됩니다.
• 모든 양의 정수 N에 대해 N 개의 연속 된 빈 슬롯이있는 무한한 수의 장소가 있습니다.

도전

당신의 도전은 다음 규칙을 가진 특별 목록을 출력하는 가장 짧은 가능한 프로그램을 작성하는 것입니다.

1. 제곱수가 아닌 인덱스가있는 모든 항목은 0으로 설정해야합니다. 따라서 첫 번째 항목은 0이 아니고 두 번째 및 세 번째는 0이되고 네 번째는 0이 아닌 것입니다.
2. 모든 합리적인 숫자는 단순화 된 부적절한 분수 (예 : 4/5 또는 144/13)의 형태입니다. 예외는 0 0입니다. 간단하게 입니다.
3. 프로그램이 충분히 길고 충분한 메모리로 실행되는 경우 모든 (양수 및 음수) 합리적인 숫자가 목록에 표시됩니다. 임의의 특정 합리적인 수에 대해, 요구되는 시간은 임의로 많지만 항상 유한 한 시간 일 수있다.
4. 무한한 시간 동안 실행하면 0이 아닌 합리적인 숫자가 두 번 나타나지 않아야합니다.

규칙 3은 무한한 수의 다른 법적 결과가 있기 때문에 약간의 변형을 허용합니다.

출력은 라인 스트림입니다. 각 줄은 일반적으로 5: 2/3첫 번째 숫자가 항목 번호이고 그 다음에 합리적인 숫자가됩니다. 참고 1: 0항상 출력의 첫 번째 줄 것입니다.

출력 스 니펫 예제 :

1: 1/1
2: 0
3: 0
4: 2/1
5: 0
6: 0
7: 0
8: 0
9: -2/1
10: 0
etc...

규칙, 규정 및 참고 사항

이것은 코드 골프입니다. 표준 코드 골프 규칙이 적용됩니다. 또한 출력에서 ​​허용되는 변형으로 인해 목록에 가능한 모든 합리적인 숫자가 정확히 한 번만 포함되고 솔루션이 올바른 이유를 최소한 보여 주어야합니다.

편집 : 소수는 도전에서 산만하기 때문에 제곱으로 변경합니다. 이는 동일한 목적을 달성하고 솔루션을 단축시킵니다.

답변

main=putStr.unlines$zip[1..](s>>=g)>>=h
s=(1,1):(s>>=f)
f(a,b)=[(a,a+b),(a+b,b)]
g x@(a,b)=[x,(-a,b)]
h(i,(a,b))=(i^2)%(u a++'/':u b):map(%"0")[i^2+1..i*(i+2)]
i%s=u i++": "++s
u=show

1: 1/1
4: -1/1
9: 1/2
16: -1/2
25: 2/1
36: -2/1
49: 1/3
64: -1/3
81: 3/2
100: -3/2
...

for i,q in enumerate(QQ):
 for j in[(i-1)^2+1..i*i]:print'%d:'%j,[0,'%d/%d'%(q.numer(),q.denom())][j==i*i]

f=lambda n:f(n/2)if n%2 else f(n/2)+f(n/2-1)if n else 1
n=i=1
while 1:
 print'%d:'%i,
 if i-n*n:s=0
 else: n+=1;s='%d/%d'%((-1)**n*f(n/2-1),f(n/2))
 print s
 i+=1

mapM_ print$join$iterate(>>=(\x->[x+1,1/(1+1/x)]))[1%1]

1 % 1
2 % 1
1 % 2
3 % 1
2 % 3
3 % 2
1 % 3
4 % 1
...

import Data.Ratio
import Control.Monad
main=mapM_ print$0:(join(iterate(>>=(\x->[x+1,1/(1+1/x)]))[1%1])>>=(\x->[-x,x]))

0 % 1
(-1) % 1
1 % 1
(-2) % 1
2 % 1
(-1) % 2
1 % 2
(-3) % 1
3 % 1
(-2) % 3
2 % 3
(-3) % 2
3 % 2
(-1) % 3
1 % 3
(-4) % 1
4 % 1
...

<?for($f=µ;$i++<$j*$j||++$j%2||(--$$f?$$f--:$f^=C);)echo"$i: ",$i==$j*$j?$j%2?$x=++$ö.~Ð.++$µ:"-$x":0,~õ;

<?for($f=µ;$i++<$j*$j||++$j%2||(--$$f?$$f--:$f^=C);)echo"$i: ",$i==$j*$j?$j%2?$x=++$ö.'/'.++$µ:"-$x":0,'
';

a=b=p=1;do for i=(p-1)^2+1:p^2-1 printf("%d: 0\n",i)end
printf("%d: %d/%d\n",p^2,a,b)
a=-a;if a>0do if b==1 b=a+1;a=1;else a++;b--;end until 1==gcd(a,b)end
p++;until 0

a=b=p=1
do
    for i=(p-1)^2+1:p^2-1
        printf("%d: 0\n",i)         # p=2,3,4: 1..3,5..8,10..15
    end
    printf("%d: %d/%d\n", p^2,a,b); # p=2,3,4: 4,9,16
    a=-a;
    if a>0                          # the rule is: after a/b, a>0 output -a/b
        do
            if b==1 b=a+1;a=1; else a++;b--; end
        until 1==gcd(a,b)
    end
    p++;
until 0