PARI's commands

[science_man_88]

Originally Posted by CRGreathouse

Also, what is sumdigits? A010888? A007953? Something else?

sumdigits is a function in the thread already pointed back to by Pi's questioning.

[CRGreathouse]

Originally Posted by science_man_88

sumdigits is a function in the thread already pointed back to by Pi's questioning.

So, neither. It's like the digital root but with sumdigits(0) = 9.

Faster code:

sumdigits(n)=n=n%9;if(n,n,9)

[science_man_88]

Originally Posted by CRGreathouse

So, neither. It's like the digital root but with sumdigits(0) = 9.

Faster code:

sumdigits(n)=n=n%9;if(n,n,9)

all i have to do is take out the return() on each to cut the time by 66% or so. and yours didn't beat mine by much on my machine ( I'll double check with multiple runs)

[science_man_88]

(12:13) gp > sumdigits1(n)=if(n%9!=0,n%9,9)
%5 = (n)->if(n%9!=0,n%9,9)
(12:15) gp > sumdigits2(n)=if(n%9!=0,return(n%9),return(9))
%6 = (n)->if(n%9!=0,return(n%9),return(9))
(12:15) gp > sumdigits3(n)=n=n%9;if(n,n,9)
%7 = (n)->n=n%9;if(n,n,9)
(12:15) gp > for(x=1,10000000,sumdigits1(x))
(12:16) gp > ##
  ***   last result computed in 6,172 ms.
(12:16) gp > for(x=1,10000000,sumdigits2(x))
(12:16) gp > ##
  ***   last result computed in 16,563 ms.
(12:16) gp > for(x=1,10000000,sumdigits3(x))
(12:17) gp > ##
  ***   last result computed in 15,141 ms.

unfortunately my first sumdigits seems most effective when added into lucaslehmers()

[CRGreathouse]

Interesting. I wonder what Pari is doing under the hood here.

Mine is still faster for large numbers, but I can't imagine why yours is faster for small numbers.

The optimal Pari (as opposed to GP) code is surely

long
digital_root(GEN n) {
  if (typ(n) != t_INT)
    pari_err(typeer, "digital_root");
  register long ret = smodis(n, 9);
  if (ret)
    return ret;
  return 9;
}

and I can't guess why your version would be closer to this than mine. Maybe I'll gp2c them later and find out.

[CRGreathouse]

Originally Posted by science_man_88

unfortunately my first sumdigits seems most effective when added into lucaslehmers()

Do you need the Lucas-Lehmer residue, or just its digital root? You can compute the latter much faster.

[science_man_88]

Originally Posted by CRGreathouse

Do you need the Lucas-Lehmer residue, or just its digital root? You can compute the latter much faster.

Digital root of the lucas lehmer residue ... really I didn't know that, Thanks. I'm just trying to limit it to a list of digital root 9 because we know the exponents must be in that group to work.

[axn]

Originally Posted by CRGreathouse

So, neither. It's like the digital root but with sumdigits(0) = 9.

Faster code:

sumdigits(n)=n=n%9;if(n,n,9)

what about

sumdigits(n)=(n-1)%9+1

?

[science_man_88]

Originally Posted by axn

what about

sumdigits(n)=(n-1)%9+1

?

using flat out print(sumdigits(x)) it ties my fastest on my machine. I'll have to check it out on the lucas test.

[science_man_88]

(15:57) gp > for(x=1,10000000,sumdigits1(x))
(16:01) gp > ##
  ***   last result computed in 6,172 ms.
(16:01) gp > for(x=1,10000000,sumdigits2(x))
(16:01) gp > ##
  ***   last result computed in 16,891 ms.
(16:01) gp > for(x=1,10000000,sumdigits3(x))
(16:01) gp > ##
  ***   last result computed in 15,312 ms.
(16:01) gp > for(x=1,10000000,sumdigits4(x))
(16:02) gp > ##
  ***   last result computed in 5,266 ms.
(16:02) gp >

we have a new winner.

[science_man_88]

(16:04) gp > for(x=1,100000,lucaslehmer2(x))
3,5,7,13,17,19,23,31,33,51,61,71,89,101,107,127,139,191,271,273,305,331,347,351,367,397,405,407
  *** _^s: user interrupt after 12,562 ms.
(16:04) gp > for(x=1,1000,lucaslehmer2(x))
3,5,7,13,17,19,23,31,33,51,61,71,89,101,107,127,139,191,271,273,305,331,347,351,367,397,405,407
(16:04) gp > ##
  ***   last result computed in 3,922 ms.
(16:04) gp > lucaslehmer2(p)= s=4;for(x=1,p-2,s=(s^2-2)%(2^p-1));if(x=p-2 && sumdigits2(s)==9,p
%21 = (p)->s=4;for(x=1,p-2,s=(s^2-2)%(2^p-1));if(x=p-2&&sumdigits2(s)==9,print1(p","))
(16:05) gp > for(x=1,1000,lucaslehmer2(x))
3,5,7,13,17,19,23,31,33,51,61,71,89,101,107,127,139,191,271,273,305,331,347,351,367,397,405,407
(16:05) gp > ##
  ***   last result computed in 3,953 ms.
(16:05) gp > lucaslehmer2(p)= s=4;for(x=1,p-2,s=(s^2-2)%(2^p-1));if(x=p-2 && sumdigits3(s)==9,p
%22 = (p)->s=4;for(x=1,p-2,s=(s^2-2)%(2^p-1));if(x=p-2&&sumdigits3(s)==9,print1(p","))
(16:05) gp > for(x=1,1000,lucaslehmer2(x))
3,5,7,13,17,19,23,31,33,51,61,71,89,101,107,127,139,191,271,273,305,331,347,351,367,397,405,407
(16:05) gp > ##
  ***   last result computed in 3,969 ms.
(16:05) gp > lucaslehmer2(p)= s=4;for(x=1,p-2,s=(s^2-2)%(2^p-1));if(x=p-2 && sumdigits4(s)==9,p
%23 = (p)->s=4;for(x=1,p-2,s=(s^2-2)%(2^p-1));if(x=p-2&&sumdigits4(s)==9,print1(p","))
(16:05) gp > for(x=1,1000,lucaslehmer2(x))
3,5,7,13,17,19,23,31,33,51,61,71,89,101,107,127,139,191,271,273,305,331,347,351,367,397,405,407
(16:05) gp > ##
  ***   last result computed in 4,000 ms.
(16:05) gp >

this is weirder and weirder lol.