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

Offset: 1

Author

Antti Karttunen, Aug 27 2014

Keywords

• nonn

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

Crossrefs

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

Programs

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

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].