

A071574


If n = kth prime, a(n) = 2*a(k) + 1; if n = kth nonprime, a(n) = 2*a(k).


9



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, 60, 18, 25, 40, 31, 52, 32, 58, 112, 96, 21, 44, 120, 36, 27, 50, 17, 80, 62, 104, 57, 64, 116, 224, 192, 42, 49, 88, 240, 72, 54, 100, 23, 34, 61, 160, 124, 208, 114, 128, 19
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

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.
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:
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 kth prime  if the bit is 0, replace k by the kth nonprime After you processed the last (i.e. least significant) bit of a(n), you've got n=k.
Example: From a(n) = 12 = 1100_2, you get 1>2>3=>6=>10; a(10)=12. Here each ">" is a step due to binary digit 1; each "=>" is a step due to binary digit 0.
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. (At least with this sequence the identity a(n) = A010051(n) mod 2 is obvious, because each prime is mapped to an odd number and each composite to an even number.  Antti Karttunen, Apr 04 2015)
For n > 1: a(n) = 2 * a(if i > 0 then i else A066246(n) + 1) + A057427(i) with i = a049084(n).  Reinhard Zumkeller, Feb 12 2014
A237739(a(n)) = n; a(A237739(n)) = n.  Reinhard Zumkeller, Apr 30 2014


LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000
Index entries for sequences that are permutations of the natural numbers


FORMULA

a(1) = 0, and for n > 1, if A010051(n) = 1 [when n is a prime], a(n) = 1 + 2*a(A000720(n)), otherwise a(n) = 2*a(1 + A065855(n)).  Antti Karttunen, Apr 04 2015


EXAMPLE

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.


MATHEMATICA

a[1] = 0 a[n_] := If[PrimeQ[n], 2*a[PrimePi[n]] + 1, 2*a[n  PrimePi[n]]]


PROG

(Haskell)
a071574 1 = 0
a071574 n = 2 * a071574 (if j > 0 then j + 1 else a049084 n) + 1  signum j
where j = a066246 n
 Reinhard Zumkeller, Feb 12 2014
(Scheme, with memoizing definecmacro)
(definec (A071574 n) (cond ((= 1 n) 0) ((= 1 (A010051 n)) (+ 1 (* 2 (A071574 (A000720 n))))) (else (* 2 (A071574 (+ 1 (A065855 n)))))))
;; Antti Karttunen, Apr 04 2015
(PARI) first(n) = my(res = vector(n), p); for(x=2, n, p=isprime(x); res[x]=2*res[x*!p(1)^p*primepi(x)]+p); res \\ Iain Fox, Oct 19 2018


CROSSREFS

Inverse: A237739.
Cf. A000720, A049084, A065855, A066246, A010051.
Compare also to the permutation A246377.
Sequence in context: A130328 A228993 A083569 * A276344 A276343 A054429
Adjacent sequences: A071571 A071572 A071573 * A071575 A071576 A071577


KEYWORD

easy,nice,nonn,look


AUTHOR

Christopher Eltschka (celtschk(AT)web.de), May 31 2002


STATUS

approved



