%I #35 Jun 05 2020 06:31:59
%S 1,2,3,8,5,4,9,10,7,12,13,20,11,6,19,14,15,22,17,18,23,30,29,16,25,24,
%T 35,26,21,34,39,40,33,28,37,32,27,50,31,44,41,46,49,36,65,38,45,52,57,
%U 68,43,42,55,58,47,48,53,62,73,60,61,54,59,64,71,66,79,56,51,76,85,72
%N Minimal permutation of the natural numbers such that the sum of squares of two consecutive terms is a prime.
%C a(1) = 1 and for n>1: a(n) = smallest m not occurring earlier such that m^2 + a(n-1)^2 is a prime; the primes are in A100209.
%C Note the same parity of a(n) and n for all terms. [_Zak Seidov_, Apr 27 2011]
%C Subsequence s(1..m) is a permutation of the natural numbers 1..m only for m=1,2,3. [_Zak Seidov_, Apr 28 2011]
%C All filtering primes (A100209) are distinct because primes of the form 4k+1 have a unique representation as the sum of two squares. [_Zak Seidov_, Apr 28 2011]
%H Zak Seidov, <a href="/A100208/b100208.txt">Table of n, a(n) for n = 1..20000</a>
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F a(A100211(n)) = A100211(a(n)) = n.
%F a(n) = sqrt(A073658(n)).
%F a(n)^2 + a(n+1)^2 = A100209(n).
%t nn = 100; unused = Range[2, nn]; t = {1}; While[k = 0; While[k++; k <= Length[unused] && ! PrimeQ[t[[-1]]^2 + unused[[k]]^2]]; k <= Length[unused], AppendTo[t, unused[[k]]]; unused = Delete[unused, k]]; t (* _T. D. Noe_, Apr 27 2011 *)
%o (Haskell)
%o import Data.Set (singleton, notMember, insert)
%o a100208 n = a100208_list !! (n-1)
%o a100208_list = 1 : (f 1 [1..] $ singleton 1) where
%o f x (w:ws) s
%o | w `notMember` s &&
%o a010051 (x*x + w*w) == 1 = w : (f w [1..] $ insert w s)
%o | otherwise = f x ws s where
%o -- _Reinhard Zumkeller_, Apr 28 2011
%o (Python)
%o from sympy import isprime
%o A100208 = [1]
%o for n in range(1,100):
%o a, b = 1, 1 + A100208[-1]**2
%o while not isprime(b) or a in A100208:
%o b += 2*a+1
%o a += 1
%o A100208.append(a) # _Chai Wah Wu_, Sep 01 2014
%o (PARI) v=[1];n=1;while(n<100,if(isprime(v[#v]^2+n^2)&&!vecsearch(vecsort(v),n),v=concat(v,n);n=0);n++);v \\ _Derek Orr_, Jun 01 2015
%Y Cf. A100209, A100211, A171964, A181723, A181730 [_Zak Seidov_, Apr 27 2011].
%Y Cf. A080478, A010051.
%K nonn,easy
%O 1,2
%A _Reinhard Zumkeller_, Nov 08 2004