A089576 Let p_k = k-th prime, let f((p_k)^n) = m where m is the largest power of p_(k+1) < (p_k)^n. a(n) = number of iterations of f to reach 1, starting from n and starting from k = 1.

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

Offset: 0

Author

Naohiro Nomoto, Dec 29 2003

Keywords

• easy
• nonn

Comments

The steps are a downward recursion in the prime powers: start at 2^n in A000961, i.e., at A000961(A024622(n)); skip to the left to the next smaller power 3^e_3 (see A024623), then to the left to the next smaller power 5^e_5, to the left to the next smaller power 7^e_7 etc., and count the steps to reach 1. - R. J. Mathar, Sep 08 2021

Examples

			a(5)=4 as f(2^5)=3^3 < 2^5, f(3^3)=5^2 < 3^3, f(5^2)=7 < 5^2 and f(7)=11^0 < 7.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..10000

Crossrefs

Row lengths of A347285.

Programs

Maple

# largest exponent m of prime(k+1)^m< prime(k)^n.
A089576f := proc(k,n)
    local pkn,pplus,m ;
    pkn := ithprime(k)^n ;
    pplus := ithprime(k+1) ;
    for m from 1 do
        if pplus^m >= pkn then
            return m-1 ;
        end if;
    end do:
end proc:
A089576 := proc(n)
    local itr,m;
    if n = 0 then
        return 0 ;
    end if;
    m := n ;
    for itr from 1 do
        m := A089576f(itr,m) ;
        if m = 0 then
            return itr ;
        end if;
    end do:
end proc:
seq(A089576(n),n=0..80) ; # R. J. Mathar, Sep 07 2021

Mathematica

Array[-1 + Length@ NestWhile[Append[#1, #2^Floor@ Log[#2, #1[[-1]]]] & @@ {#, Prime[Length@ # + 1]} &, {2^#}, #[[-1]] > 1 &] &, 71, 0] (* Michael De Vlieger, Sep 08 2021 *)

Extensions

More terms from Michael De Vlieger, Sep 08 2021