[seqfan] Re: cute Superseeker hit

[Wouter Meeussen]

Thanks Don,

we'll take that as sufficient proof ( and add it as a txt file if you so 
permit ) and comment A061303 accordingly.
Alonso, maybe I should put a link in  A009195   "GCD(n, phi(n))"  also?

Wouter.

-----Original Message----- 
From: Don Reble
Sent: Monday, March 17, 2014 7:04 PM
To: Sequence Fanatics Discussion list
Subject: [seqfan] Re: cute Superseeker hit

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


_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/