login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A071574 If n = k-th prime, a(n) = 2*a(k) + 1; if n = k-th nonprime, a(n) = 2*a(k). 8
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 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.

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.

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 definec-macro)

(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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 13 09:05 EST 2017. Contains 295957 sequences.