반 에크 수열 계산기

a(0)=0에서 시작해, 직전 항 a(n-1)을 봅니다. 그 값이 그 전에 한 번도 나온 적 없으면 a(n)=0이고, k번째 자리에서 마지막으로 나온 적 있으면 a(n)=(n-1)-k(그 자리와의 간격)입니다.

다음 항을 정할 때 필요한 정보가 딱 그것뿐이기 때문입니다. 값마다 최근 등장 위치를 해시맵에 담아 두면, 매 단계마다 배열 전체를 뒤지지 않고 O(1)로 조회할 수 있습니다. 이 계산기는 O(n²)로 배열을 매번 훑는 무식한 방법과 대조해 같은 결과가 나오는 것을 확인했습니다.

a(n)의 값을 정한 "다음에" 방금 본 자리를 기억해야 합니다. 순서를 뒤집어 먼저 기억부터 갱신하면, 직전 항이 방금 자기 자신이 나온 자리를 자기 자신의 "이전" 위치로 착각해 간격이 항상 0으로 고정되고, 그 뒤로는 영원히 0만 나오는 틀린 수열이 됩니다.

둘 다 "자기서술 수열"로 묶이지만 규칙은 전혀 다릅니다. 레카만 수열(edu/recaman-sequence)은 뺄셈·덧셈 중 하나를 골라 새로운 위치로 점프하는 수열이고, 반 에크 수열은 과거의 자신을 돌아봐 값이 마지막으로 나온 간격을 재는 수열입니다.

될 수 없습니다. 값이 항상 "자리 사이의 간격"이라 0 이상의 정수로만 나옵니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.