Assembly pgm for the decomposition of primes

reismann at reismann at
Sat Apr 21 15:28:54 CEST 2007

Dear SeqFans,

My friend Fabien Sibenaler realized an Assembly program implementing the new
algorithm that gives the decomposition of a prime number (prime = weight * level
+ gap, or A000040(n) = A117078(n) * A117563(n) + A001223(n)).

This pgm is faster than the previous pgm said "naïf" for prime numbers
classified by level.
Ex (PIV 3 GHz, 512 Mo RAM) :
Old pgm :
Number     : 979872743
Gap        : 204
Weight     : 979872539
Level      : 1
Time in ms : 116656

New pgm :
Number     : 979872743
Gap        : 204
Weight     : 979872539
Level      : 1
Time in ms : 16

The principle of the new algo :
We look for the odd weights until sqrt(p) (1 red) and if we did not find the
decomposition, we look for it by levels until (ln p)^2 by beginning with the
highest level (2 red).
This limit (ln p)^2 is arbitrary and can be improved.
Whith the "naïf" algo, we looked for the odd weights until p-g (1 black) :
The decomposition of primes in weight * level + gap is a generalisation of the
Eratosthenes sieve :

Assembly pgm : (the zip file contains exe and
source code).
Neil, the link on A117078 is OK.
or on the "Download" page :

With this pgm I found a prime of level(1,24) :
p(28106444831) - p(28106444830) = p(28106444830) - p(28106444830 - 24)
738832928467 - 738832927927 = 738832927927 - 738832927387 = 540 = 6 * 90
p(28106444830) is of level 1 in in A117563,
p(28106444830) = 738832927927 is of level(1,24).

With the Java pgm, I obtained a table of 25 million lines in 2h49min  (PIV 3
GHz, 512 Mo RAM).


Rémi Eismann

Brendan said:
Valery's observation suggests that the search engine should allow
a query that finds all sequences which are term-wise multiples
of a given sequence.
for any single number. So you could do that for several
terms of your sequence (assuming these are large numbers)
and look for a common thread.

Straightforward duplicates:

A056260 and A101149
A088269 and A103993
A089374 and A110794
A103277 and A121451
A117300 and A117134
A083538 and A083543
A023701 and A043331
A023723 and A043350
A061839 and A095241 and possibly A065779
A023739 and A043366
A098769 and A098900

Possible duplicates:

A061068 and A120744
A056215 and A098677


Will the sequences A068310 and A086485 ever differ? Glancing at the problem
I think they will at some value for n, but n would probably have to be very
large. If not, then these are duplicates. On a similar note, A106766 and
A119892 will probably differ at some point, too. It is kind of interesting
that they match as well as they do.

More information about the SeqFan mailing list