login
Lexicographically earliest sequence such that |a(n+1)-a(n)| is a square > 1 (for all n) and no number occurs twice; a(0) = 0.
7

%I #33 Feb 09 2025 12:19:54

%S 0,4,8,12,3,7,11,2,6,10,1,5,9,13,17,21,25,16,20,24,15,19,23,14,18,22,

%T 26,30,34,38,29,33,37,28,32,36,27,31,35,39,43,47,51,42,46,50,41,45,49,

%U 40,44,48,52,56,60,64,55,59,63,54,58,62,53,57,61,65,69,73,77,68,72,76,67,71,75,66,70,74,78,82,86,90,81,85,89,80,84,88,79,83,87

%N Lexicographically earliest sequence such that |a(n+1)-a(n)| is a square > 1 (for all n) and no number occurs twice; a(0) = 0.

%C A variant is given by A277617, defined in the same way but starting with a(1) = 1. Another variant is A277618, which is defined in a similar way, but with primes instead of squares.

%C Yet another version is A377091, with an interesting graph. - _N. J. A. Sloane_, Dec 25 2024

%C It turns out that the steps a(n+1)-a(n) are either +4 or -9, no other squares occur as distances between successive terms. Indeed, one finds a(13) = 13 and all numbers from 0 to 12 occur as a(n) for 0 <= n <= 12. So there are no "holes", which entails the periodicity. More precisely, a({0, ..., 13k-1}) = {0, ..., 13k-1} and a(13k) = 13k for all k. This also implies that the sequence is a permutation of the nonnegative integers. - _M. F. Hasler_, Oct 24 2016

%H N. J. A. Sloane, <a href="/A277616/b277616.txt">Table of n, a(n) for n = 0..10000</a>

%H <a href="/index/Rec#order_14">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,0,0,0,0,0,0,0,0,0,1,-1).

%F a(n+13) = a(n)+13 for all n.

%F From _Chai Wah Wu_, Mar 30 2023: (Start)

%F a(n) = a(n-1) + a(n-13) - a(n-14) for n > 13.

%F G.f.: x*(4*x^12 + 4*x^11 + 4*x^10 - 9*x^9 + 4*x^8 + 4*x^7 - 9*x^6 + 4*x^5 + 4*x^4 - 9*x^3 + 4*x^2 + 4*x + 4)/(x^14 - x^13 - x + 1). (End)

%e The possible (absolute) differences between subsequent terms are the squares larger than one, i.e., { 4, 9, 16, ... }.

%e After 0, the smallest possibility is 0 + 2^2 = 4, the next one is 4 + 2^2 = 8, and then 8 + 2^2 = 12. Now the next term is 12 - 3^2 = 3, thereafter 3 + 2^2 = 7, etc.

%e In a similar way, 11 is followed by 11 - 3^2, and 10 is followed by 10 - 3^2 = 1.

%e Thereafter, the next step of -9 will be after 25.

%e The sequence of steps (first differences) consists of repetitions of the 13 terms (4, 4, 4, -9, 4, 4, -9, 4, 4, -9, 4, 4, 4) which sum to 13.

%p A277616 := proc(n) local L,i,t1; option remember;

%p L := [0, 4, 8, 12, 3, 7, 11, 2, 6, 10, 1, 5, 9, 13];

%p if n <= 13 then return(L[n+1]) else A277616(n-13)+13; fi; end; # _N. J. A. Sloane_, Jan 12 2025

%t LinearRecurrence[{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1}, {0, 4, 8, 12, 3, 7, 11, 2, 6, 10, 1, 5, 9, 13}, 100] (* _Paolo Xausa_, Jan 16 2025 *)

%o (PARI) {u=[a=0];(chk(n)=(!#u||(n>u[1]&&!setsearch(u,n)))&&(u=setunion(u,[n]))&&!while(#u>1&&u[2]==u[1]+1,u=u[^1]));for(n=1,99,print1(a",");for(k=-sqrtint(a+!a-1),9e9,k^2>1||next;chk(a+k*abs(k))||next;a+=k*abs(k);break))} \\ _M. F. Hasler_, Oct 23 2016

%o (PARI) A277616(n,i=[0,4,8,12,3,7,11,2,6,10,1,5,9])=i[n%#i+1]+n\#i*#i \\ _M. F. Hasler_, Oct 24 2016

%Y Cf. A034175, A277617, A277618, A377091.

%K nonn,easy,changed

%O 0,2

%A _Eric Angelini_, Oct 23 2016