A158918 n, ps(n), ps^2(n), ..., ps^9(n) forms an increasing ps-sequence of length 10.

12900, 737100, 772176, 832050, 844032, 844992, 864976, 872208, 879984, 887088, 926400, 939900, 954828, 960372, 962724, 964800, 967500, 969444, 972804, 973296, 975828, 976144, 980000, 982044, 984064

Offset: 1

Author

Matthijs Coster, Mar 30 2009

Keywords

• nonn

Comments

ps (read phi-sigma) is the consecution of the sigma (sum of divisors) and Euler totient function.

The problem raises from the aliquot sequences. In the case of aliquot sequences we calculate the next element by calculating the sum of the divisors, and afterwards subtract the original number n.

Instead of subtract n we apply the totient function in order to get ps-sequences. Fast decreases can appear if the sum of divisors consist of many different small primes.

In fact ps-sequences end very fast in cycles, often cycles of small length.

I didn't find an increasing ps-sequence of length > 12.

Examples

			12900 = 2^2*3*5^2*43, s(12900) = 7*4*31*44, ps(12900) = 6*30*8*10 = 2^6*3^2*5^2 = 14400;
s(14400) = 127*13*31, ps(14400) = 126*12*30 = 2^4*3^4*5*7 = 45360; ...
		

Programs

Sage

#(not fast!)
def phi(L):
    m = 1
    for l in L:
        m = m * (l[0]-1)
        for i in (1..l[1]-1):
            m = m * l[0]
    return m
def sigma(L):
    m = 1
    for l in L:
        q = 1
        for i in (0..l[1]):
            q = q * l[0]
            m = m * (q-1) / (l[0]-1)
    return m
cc = 8
START = 2
END = 10000000
for f0 in (START..END):
    c = 0
    f = f0
    Lf = list(factor(f))
    s = sigma(Lf)
    Ls = list(factor(s))
    f1 = phi(Ls)
    while f < f1:
        c = c + 1
        f = f1
        Lf = list(factor(f))
        s = sigma(Lf)
        Ls = list(factor(s))
        f1 = phi(Ls)
    if c > cc:
        print(c, ":", f0)