|
%I
%S 0,1,3,2,7,6,5,4,14,12,15,10,13,8,28,24,11,30,9,20,26,16,29,56,48,22,
%T 60,18,25,40,31,52,32,58,112,96,21,44,120,36,27,50,17,80,62,104,57,64,
%U 116,224,192,42,49,88,240,72,54,100,23,34,61,160,124,208,114,128,19
%N If n = k-th prime, a(n)=2*a(k)+1; if n = k-th nonprime, a(n)=2*a(k).
%C The recursion start is implicit in the rule, since the rule demands that a(1)=2*a(1). All other terms are defined through terms for smaller indices until a(1) is reached.
%C a(n) is a bijective mapping from the positive integers to the nonnegative integers. Given the value of a(n), you can get back to n using the following algorithm:
%C Start with an initial value of k=1 and write a(n) in binary representation. Then for each bit, starting with the most significant one, do the following: - if the bit is 1, replace k by the k-th prime - if the bit is 0, replace k by the k-th nonprime After you processed the last (i.e. least significant) bit of a(n), you've got n=k.
%C Example: From a(n)=12=bin(1100),you get 1->2->3=>6=>10; a(10)=12. Here -> are the steps due to binary digit 1, => are the steps due to binary digit 0.
%C The following sequences all appear to have the same parity (with an extra zero term at the start of A010051): A010051, A061007, A035026, A069754, A071574. - _Jeremy Gardiner_, Aug 09, 2002
%H T. D. Noe, <a href="/A071574/b071574.txt">Table of n, a(n) for n=1..10000</a>
%e 1 is the first nonprime, so f(1) = 2*f(1), therefore f(1) = 0; 2 is the first prime, so f(2) = 2*f(1)+1 = 2*0+1 = 1; 4 is the 2nd nonprime, so f(4) = 2*f(2) = 2*1 = 2
%t a[1] = 0 a[n_] := If[PrimeQ[n], 2*a[PrimePi[n]] + 1, 2*a[n - PrimePi[n]]]
%K easy,nice,nonn
%O 1,3
%A Christopher Eltschka (celtschk(AT)web.de), May 31 2002
|
