login
Minimal permutation of the natural numbers such that the sum of squares of two consecutive terms is a prime.
14

%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