[seqfan] Algorithms to decompose a prime number into weight * level + jump

[reismann at free.fr]

Hi seqfans,

I updated and improved the programs java to decompose a prime number into weight * level + jump. There are 3 algorithms : 
Naive algo : 
for (int k = 3; k <= ln; k += 2) {
    if ((prime % k) == jump) {
	weight = k;
	level = ln / k;
	break;
    }
}

Naive algo wih primality test : it's the same as the naive algo but with a primality test on l(n) to find directly the primes of level 1.

Algo "newSieve" : 
// We look for the primes classified by weight
// limWeight : weight <= sqrt(l(n))
int limWeight = (int) (Math.floor(Math.sqrt(ln) + 1));
for (int k = 3; k <= limWeight; k += 2) {
	if ((prime % k) == jump) {
		weight  = k;
		level = ln / k;
		p_n[l_ordre] = true;
		break;
	}
}
// We look for the primes classified by level
if (p_n[l_ordre] == false) {
     // limLevel : level <= jump - 1
     int limLevel = jump - 1;
     for (int l = limLevel; l >= 1; l -= 2) {
	   if ((prime  % (ln / l)) == jump) {
		weight = ln / l;
		level = l;
		p_n[l_ordre] = true;
		break;
	   }
     } 
}
Algorithm "newSieve" is the faster.
You can find the programs and a graph to explain the algorithms on this page :
http://reismann.free.fr/algo_en.php

Have a nice day,

Rémi Eismann