[seqfan] Re: cute Superseeker hit

[Don Reble]

> `Super' hit on  Amarnath Murthy's A061303(n)+1
> (see http://oeis.org/A061303 )
> with gcd( n!, Phi(n!) )===gcd( (n+1)!, Phi((n+1)!) )

    Let's call it  gcd{(n-1)!, Phi[(n-1)!]} = gcd{n!, Phi[n!]}
    so that the sequences start out the same.

    If n is prime,     Phi[n!] = (n-1) * Phi[(n-1)!];
    if n is composite, Phi[n!] =   n   * Phi[(n-1)!]
        (because all prime factors of n have already appeared in (n-1)!).
    n! = n * (n-1)!, so at composite n, that gcd increases n-fold.

    If n is prime, the gcd might increase or not: see what happens at n=7:

    n   n!              phi(n!)                 gcd
    -   -----------     -----------------       -------
    6   2^4 3^2 5       2^4 3                   2^4 3
    7   2^4 3^2 5 7     2^4 3 6 = 2^5 3^2       2^4 3^2

    The gcd increased because (7-1) brought in a factor of 3 which was
    in n! but missing in phi(6!). (7) did that because it's the first
    3k+1 prime. Henceforth the phi's will have at least as many 3-powers
    as n!.

    I see that Wouter's (incremented) sequence contains the primes, but
    not the first pk+1 prime for any prime p. But those are the very
    primes eliminated by A061303's S() sequences.

    So I say they're the same sequence.

-- 
Don Reble  djr at nk.ca