A246348 - OEIS

A246348

a(1)=1, a(p_n) = 1 + a(n), a(c_n) = 1 + a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n); Also binary width of terms of A135141.

1, 2, 3, 2, 4, 3, 3, 4, 3, 5, 5, 4, 4, 4, 5, 4, 4, 6, 5, 6, 5, 5, 4, 5, 6, 5, 5, 7, 6, 6, 6, 7, 6, 6, 5, 6, 5, 7, 6, 6, 5, 8, 5, 7, 7, 7, 6, 8, 7, 7, 6, 7, 5, 6, 8, 7, 7, 6, 5, 9, 7, 6, 8, 8, 8, 7, 6, 9, 8, 8, 7, 7, 6, 8, 6, 7, 9, 8, 6, 8, 7, 6, 5, 10, 8, 7, 9, 9, 6, 9, 8, 7, 10

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

If n = 1, the result is 1, otherwise, if n is prime, compute the result for that prime's index (A000720 or A049084) and add one, and if n is composite, compute the result for that composite's index (A065855) and add one.

a(n) tells how many calls (including the toplevel call) are required to compute A135141(n) or A246377(n) with a simple (nonmemoized) recursive algorithm as employed for example by Robert G. Wilson v's Mathematica-program of Feb 16 2008 in A135141 or Antti Karttunen's Scheme-proram in A246377.

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..32998

FORMULA

a(1) = 1, and for n >= 1, if A010051(n)=1 [that is, when n is prime], a(n) = 1 + a(A000720(n)), otherwise a(n) = 1 + a(A065855(n)). [A000720(n) and A065855(n) tell the number of primes, and respectively, composites <= n].

a(n) = A246369(n) + A246370(n).

a(n) = A070939(A135141(n)) = 1 + floor(log_2(A135141(n))). [Sequence gives also the binary width of terms of A135141].

a(n) = A070939(A246377(n)). [Also for 0/1-swapped version of that sequence].

PROG

(PARI)

\\ Compute the b-files for both the positions of records (A246346) and their values (A246347) and also for A246348 (somewhat naively):

default(primelimit, (2^31)+(2^30));

A070939 = n->#binary(n)+!n \\ From M. F. Hasler

A135141(n) = if(1==n, 1, if(isprime(n), 2*A135141(primepi(n)), 1+(2*A135141(n-primepi(n)-1))));

A246348(n) = A070939(A135141(n));

prevmax = -1; i = 0; for(n=1, 123456, if((k=A135141(n)) > prevmax, prevmax = k; i++; write("b246346.txt", i, " ", n); write("b246347.txt", i, " ", k)); write("b246348.txt", n, " ", A246348(n)));

(Scheme, two versions, second being a direct recurrence employing memoizing definec-macro from Antti Karttunen's IntSeq-library)

(define (A246348 n) (A070939 (A135141 n)))

(definec (A246348 n) (cond ((= 1 n) 1) ((= 1 (A010051 n)) (+ 1 (A246348 (A000720 n)))) (else (+ 1 (A246348 (A065855 n))))))

CROSSREFS

Cf. A000040, A002808, A000720, A065855, A070939, A135141, A246346, A246347, A246369, A246370, A246377.

Sequence in context: A341041 A361660 A318046 * A205782 A070296 A303581

Adjacent sequences: A246345 A246346 A246347 * A246349 A246350 A246351

KEYWORD

nonn

AUTHOR

Antti Karttunen, Aug 27 2014

STATUS

approved