Prime Puzzle #190

[T.Rex]

Originally Posted by rogue

... my own PPC ASM version

Seems you have a PowerPC version of your program. Can you make it available so that I see how fast it runs on Linux/Power5+ 1.65 GHz ?
T.

[rogue]

Originally Posted by T.Rex

Seems you have a PowerPC version of your program. Can you make it available so that I see how fast it runs on Linux/Power5+ 1.65 GHz ?
T.

See attached. You need GMP installed and you need to compile with -m64.

BTW, searched to 2e11 with no new solutions. I stopped as I don't expect another solution anytime soon. I could run it to 1e13 in a couple of weeks, but why waste my resources. Maybe I'll come back to it in the future, but I've got too many things on my plate at the moment that require horsepower.

[T.Rex]

Thanks.
But ... how do you compile it ?
gcc -m64 consec.c expmod.s mulmod.s
shows problems with // comments in .s files and also when I've removed them (I'm not an expert in compiling assembler ...).
T.

With // comments:
expmod.s:1: Error: junk at end of line, first unrecognized character is `/'

Without // comments:
expmod.s:6: Error: unsupported relocation against r26

[rogue]

Originally Posted by T.Rex

Thanks.
But ... how do you compile it ?
gcc -m64 consec.c expmod.s mulmod.s
shows problems with // comments in .s files and also when I've removed them (I'm not an expert in compiling assembler ...).
T.

With // comments:
expmod.s:1: Error: junk at end of line, first unrecognized character is `/'

Without // comments:
expmod.s:6: Error: unsupported relocation against r26

Try the compiler option:
-mregnames

After that, use google.

[Maybeso]

Uh, why do your programs list 7 and 11? They are not solutions.

Originally Posted by R. Gerbicz

I've also written a program.
Rogue, the last time is the total computation time=687 seconds up to 2^29,
(this is about 5*10^8) on my machine.

C:\>p190
Searching for solutions up to 2^29
p=2 Time=0.000 sec.
p=3 Time=0.000 sec.
p=5 Time=0.000 sec.
p=7 Time=0.000 sec.
p=11 Time=0.000 sec.
p=8167 Time=0.015 sec.
p=371321 Time=0.468 sec.
Time=687.640 sec.

[R. Gerbicz]

Originally Posted by Maybeso

Uh, why do your programs list 7 and 11? They are not solutions.

I'm checking (S(p)*X2)%p, so if S(p) is divisible by p then I get that solution but we can get some false solutions (like 7 and 11), because it is possible that X2 is divisible by p, but S(p) isn't divisible by p. Note that there wasn't other false solutions up to 2e11 or something like that, what Rogue searched and it is easy to write a fast independent program to see if it is a good solution or not.

[Maybeso]

Ok, that makes sense. I was thinking that the magnitude of p compared to that of the lcm factors would prevent false hits for small p, but it seems to prevent them for large p.

Some of the lcm factors:

7 11 13 37 41 53 73 79 101 137 239 271 4649 9091 9901 21649 333667 513239 909091 265371653 ...

Strange that only 7 and 11 create hits.

I have access to a PICK OS machine, which is string based. Programs, numbers and variables are all dynamic length strings. So I wrote a brute force program for this puzzle in compiled PICK BASIC, with the inner loop like this:

  M = 1
  FOR N = 2 TO P
    M = MOD(M:N, P)
  NEXT N
  IF M ELSE PRINT P

But the machine is an emulation running on linux, and it's multi-user, so although the code looks pretty, it doesn't run much faster than a program using normal integers and 'manual' concatenation. I do get arbitrary length numbers for free, but time is still the main obstacle.

ps. I could port over your ingenius method, but since it doesn't require concatenation, there would be no advantage.

Bruce