login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

a(1) = 1; for n > 1, a(n) is the smallest unused positive number such that (a(n-1) AND a(n)) = 0 if a(n-1) is prime, otherwise (a(n-1) AND a(n)) = a(n-1), where AND is the binary AND operation.
2

%I #16 Oct 03 2024 07:35:10

%S 1,3,4,5,2,8,9,11,16,17,6,7,24,25,27,31,32,33,35,39,47,64,65,67,12,13,

%T 18,19,36,37,10,14,15,63,127,128,129,131,20,21,23,40,41,22,30,62,126,

%U 254,255,511,1023,2047,4095,8191,8192,8193,8195,8199,8207,8223,8255,8319,8447,256,257,26,58,59,68,69,71,48,49,51,55,119,247,503,512,513,515,519

%N a(1) = 1; for n > 1, a(n) is the smallest unused positive number such that (a(n-1) AND a(n)) = 0 if a(n-1) is prime, otherwise (a(n-1) AND a(n)) = a(n-1), where AND is the binary AND operation.

%C The long term behavior of the terms is dominated by the appearance of the Mersenne primes. This is due to composite numbers appearing which are 1 less than a power of 2, i.e., their binary representation consists of all 1's. Therefore the next term must be 1 less than the next power of 2 to satisfy (a(n-1) AND a(n)) = a(n-1). This pattern repeats until such a number is prime, i.e., a Mersenne prime, at which point the next term will be 1 more than this prime, after which the terms can eventually return to smaller values.

%C Due to the above behavior it is unknown if all numbers eventually appear, but assuming the number of Mersenne primes is infinite, it is likely all eventually will. In the first 100 terms the fixed points are 1, 71, 463, although more likely exist.

%H Scott R. Shannon, <a href="/A375829/b375829.txt">Table of n, a(n) for n = 1..1100</a>

%e a(7) = 9 as a(6) = 8 = 1000_2 is not prime, and ((9 = 1001_2) AND 1000_2) = 1000_2 = 8.

%e a(9) = 16 as a(8) = 11 = 1011_2 is prime, and ((16 = 10000_2) AND 1011_2) = 0.

%Y Cf. A375828, A000668, A109812, A007088, A115510, A000040, A353989.

%K nonn

%O 1,2

%A _Scott R. Shannon_, Aug 30 2024