A065770 Number of prime cascades to reach 1, where a prime cascade (A065769) is multiplicative with a(p(m)^k) = p(m-1) * p(m)^(k-1).

0, 1, 2, 2, 3, 2, 4, 3, 3, 3, 5, 3, 6, 4, 3, 4, 7, 3, 8, 3, 4, 5, 9, 4, 4, 6, 4, 4, 10, 3, 11, 5, 5, 7, 4, 4, 12, 8, 6, 4, 13, 4, 14, 5, 4, 9, 15, 5, 5, 4, 7, 6, 16, 4, 5, 4, 8, 10, 17, 4, 18, 11, 4, 6, 6, 5, 19, 7, 9, 4, 20, 5, 21, 12, 4, 8, 5, 6, 22, 5, 5, 13, 23, 4, 7, 14, 10, 5, 24, 4, 6, 9, 11

Offset: 1

Author

Henry Bottomley, Nov 19 2001

Keywords

• nonn

Comments

It seems that a(n) <= A297113(n) for all n. Of the first 10000 positive natural numbers, 6454 are such that a(n) = A297113(n). - Antti Karttunen, Dec 31 2017

Also one plus the maximum number of unit steps East or South in the Young diagram of the integer partition with Heinz number n > 1, starting from the upper-left square and ending in a boundary square in the lower-right quadrant. The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). - Gus Wiseman, Apr 06 2019

Examples

			a(50) = 4 since the cascade goes from 50 = 2^1 * 5^2 to 15 = 3^1 * 5^1 to 6 = 2^1 * 3^1 to 2 = 2^1 to 1.
From _Gus Wiseman_, Apr 06 2019: (Start)
The partition with Heinz number 7865 is (6,5,5,3), with diagram
  o o o o o o
  o o o o o
  o o o o o
  o o o
which has longest path from (1,1) to (5,3) of length 6, so a(7865) = 7.
(End)
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..16384
• FindStat, St000384: The maximal part of the shifted composition of an integer partition

Crossrefs

Cf. A065769.

Differs from A297113 for the first time at n=20, where a(20) = 3, while A297113(20) = 4.

Cf. A001221, A001222, A052126, A056239, A064989, A112798, A174090, A257990, A325166, A325167, A325169.

Programs

Mathematica

Table[If[n==1,0,Max@@Total/@Position[PadRight[ConstantArray[1,#]&/@Sort[Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]],Greater]],1]-1],{n,100}] (* Gus Wiseman, Apr 06 2019 *)

Scheme

(definec (A065770 n) (if (= 1 n) 0 (+ 1 (A065770 (A065769 n))))) ;; Antti Karttunen, Dec 31 2017

Formula

Inverse of primes, powers of 2 and primorials in sense that a(A000040(n))=n; a(A000079(n))=n; a(A002110(n))=n. If n>0: a(3^n)=n+1; a(2^n*3^k)=n+k; a(p(k)^n)=n+k-1; a(n!)=A022559(n).

a(1) = 0; and for n > 1, a(n) = 1 + A065769(n). - Antti Karttunen, Dec 31 2017