A038122 Start with {1,2,...,n}, replace any two numbers a,b with |a^2-b^2|, repeat until single number k remains; a(n) = minimal value of k.

1, 3, 0, 16, 15, 63, 8, 0, 3, 1, 0, 0, 1, 3, 0, 4, 3, 3, 4, 0, 3, 1, 0, 0, 1, 3, 0, 4, 3, 3, 4, 0, 3, 1, 0, 0, 1, 3, 0, 4, 3, 3, 4, 0, 3, 1, 0, 0, 1, 3, 0, 4, 3, 3, 4, 0, 3, 1, 0, 0, 1, 3, 0, 4, 3, 3, 4, 0, 3, 1, 0, 0, 1, 3, 0, 4, 3, 3, 4, 0, 3, 1, 0, 0, 1, 3, 0, 4, 3, 3, 4, 0, 3, 1, 0, 0, 1, 3, 0, 4, 3, 3, 4, 0

Offset: 1

Author

R. K. Guy

Keywords

• nonn
• nice
• easy

Comments

Due mostly to the efforts of Dean Hickerson, supported by David W. Wilson and Michael Kleber, it is now known that this has period 12 beginning at n=8.

Examples

			a(2) = 3 from (1,2); a(3) = 0 from ((1,2),3); a(4) = 16 from (((1,2),3),4); a(5) = 15 from ((((2,3),5),1),4)
a(6) = 63 from (((1,4),(3,5)),(2,6)) [ _Michael Kleber_ ]
a(7) = 8 from (((((4,5),6),(2,7)),1),3) [ Kleber ]
a(8) = 0 from ((((4,5),7)(2,6))((1,3),8)) [ Guy ]
a(9) = 3 from (2,(1,(((6,7),((3,4),8)),(5,9)))) [ Kleber ]
a(10)= 1 from ((((((((4,5),9),6),(8,10)),2),3),7),1) [ This and the following are due to _Dean Hickerson_ ]
a(11)= 0 from ((((((3,7),(9,11)),6),(8,10)),(1,2)),(4,5))
a(12)= 0 from ((((((1,3),7),(8,10)),(((5,6),9),(11,12))),2),4)
a(13)= 1 from (((((((((3,7),(9,11)),6),(8,10)),5),(12,13)),2),4),1) ...
		

Links

• Dean Hickerson and Michael Kleber, Reducing a Set by Subtracting Squares, J. Integer Sequences, Vol. 2, 1999, #4.
• Index entries for linear recurrences with constant coefficients, signature (0,0,1,0,0,-1,0,0,1).

Programs

Mathematica

LinearRecurrence[{0,0,1,0,0,-1,0,0,1},{1,3,0,16,15,63,8,0,3,1,0,0,1,3,0,4},120] (* Harvey P. Dale, Jul 29 2015 *)

PARI

a(n)=if(n<4||n>7, n*(n+1)/2%6, [16, 15, 63, 8][n-3]) \\ Charles R Greathouse IV, Feb 10 2017

Python

def A038122(n): return (16,15,63,8)[n-4] if 3>1)%6 # Chai Wah Wu, Apr 17 2025

Formula

For n<4 and n>7, a(n) = n*(n+1)/2 mod 6 = A010875(A000217(n)). - Henry Bottomley, Feb 24 2003

a(n) = a(n-3)-a(n-6)+a(n-9) for n>16. - Colin Barker, Oct 01 2014

G.f.: x*(4*x^15 +60*x^14 +12*x^13 +8*x^12 -60*x^11 -12*x^10 -8*x^9 +60*x^8 +12*x^7 +7*x^6 -63*x^5 -12*x^4 -15*x^3 -3*x -1) / ((x -1)*(x^2 +1)*(x^2 +x +1)*(x^4 -x^2 +1)). - Colin Barker, Oct 01 2014