Loading ...
Sorry, an error occurred while loading the content.

Re: Small prime divisors of very large numbers

Expand Messages
  • Mark Underwood
    ... Feature number one, where some primes stay forever as divisors, is a natural consequence. Specifically, if a factor appears twice in a row at two
    Message 1 of 70 , Jul 2, 2009
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "David Broadhurst" <d.broadhurst@...> wrote:
      >
      > --- In primenumbers@yahoogroups.com,
      > "Mark Underwood" <mark.underwood@> wrote:
      >
      > > Here's a hint: (n-1) is a factor of (n^n-n).
      >
      > The stakes have risen, Mark.
      >
      > You have to explain 3 features of the data that
      > Richard Heylen has exposed:
      >
      > 1) some primes stay as divisors at successive higher powerings;
      > 2) some disappear for ever after a single division;
      > 3) some pop in, pop out, then pob back, then stay put.
      >
      > To how many of those features of the data does your
      > gnomic "hint" apply? If not to all 3, then why not?
      >
      > Thanks, in any case, for your interest
      >
      > David
      >

      Feature number one, where some primes stay forever as divisors, is a natural consequence. Specifically, if a factor appears twice in a row at two successive powerings, it will remain from then on. Why some prime divisors appear only once while others flit in and out and others never make an appearance, those are details that could be worked out I'm sure.


      Mark
    • Maximilian F. Hasler
      Dear all, I come back to this topic, looking for a working pow_mod . This : {mypmod(b,n,p)=local(m=[p],f=0); while(n=n-1,m=concat(eulerphi(m[1]),m));
      Message 70 of 70 , Mar 23, 2014
      • 0 Attachment
        Dear all,
        I come back to this topic, looking for a working "pow_mod".
        This :
        {mypmod(b,n,p)=local(m=[p],f=0);
        while(n=n-1,m=concat(eulerphi(m[1]),m));
        for(p=n=1,#m,n=lift(Mod(b,m[p])^n);
        if(f=f+(n*log(b)>=log(m[p])),n=n+m[p]));n%m[#m];}

        yields:
        mypmod(2,3,5)
        = 2
        but 2^2^2 % 5 = 16 % 5 = 1.
        (and idem for 2^2^2^2 - of course.).

        David gave some other code, in
        https://groups.yahoo.com/neo/groups/primenumbers/conversations/topics/20526
        :
        "
        Below is a Pari-GP procedure "pmod(a,m)" to compute
        a[1]^(a[2]^(a[3]^ ... ^(a[k-1]^a[k]) ... ) modulo m
        where the modulus "m" need not be prime.
        (...)
        {pmod(a,m)=local(k,q,t);k=#a;q=[m];t=a[k];
        for(j=2,k-1,q=concat(eulerphi(q[1]),q));
        for(j=1,k-1,t=Mod(a[k-j],q[j])^lift(t));t}
        "
        Although this may work for prime m
        (at least, pmod([2,2,2],5) = Mod(1,5) as should),
        it gives:

        pmod([2,2,2],4)
        = Mod(1, 4)
        which is most certainly wrong.

        So, to put it short, has anyone a working pmod() in his "library" ?

        Thanks in advance!
        Maximilian


        --- In primenumbers@yahoogroups.com, "David Broadhurst"
        <d.broadhurst@...> wrote:

        > fail

        (...)

        I consider that his code should not be trusted.

        David
      Your message has been successfully submitted and would be delivered to recipients shortly.