Web log de Serge Boisse
On line depuis 1992 !
Résumé : recherche d'un algorithme de factorisation rapide.
Ceci est une recherche en cours. Elle n'est pas encore terminée. Cette page est susceptible d'évoluer dans le futur...
cf facto par insertion de zeros (Fichier sur D)(lien privé) (lien privé)
Dans ce qui suit,
On utilisera parfois la typographie Latex, comme x**2
.
On notera a^b
ou
a^a=0
On notera **
la fonction puissance : 2**3=8
ou en Latex
On notera %
la fonction modulo : 13%4
= 1
on notera aussi g(n)
le code Gray de n : g(n)=n^(n/2)
où n/2 = n>>1
c'est à dire le décalage des bits de n de 1 cran à droite sans virgule. Par exemple g(554)=831.
On peut démontrer que
g(a^b) = g(a)^g(b)
L'inverse de cette fonction g est l'intégrale de parité chère à Gérard Langlet qui en a fait l'analyse exhaustive. Si nous appelons ig cette fonction réciproque de g, on peut la calculer ainsi :
ig(x) = ig2(0,floor(x))
ig2(r,n) = (n<=0) ? r: ig2(r^n, n/2)
Et on a n= g(ig(n)) = ig(g(n))
et ig(a^b) = ig(a)^ig(b)
Dans ce qui suit a,b,c,d,n,m
sont des entiers positifs. On note a\b
ou
Par exemple
123 = 1 1 1 1 0 1 1
25 = 0 0 1 1 0 0 1
123\25 = 10101111001011 = 11211 en base 10
a\b
avec gnuplot :
ins(a,b) = (a==0&&b==0)?0:(b&1)+2*(a&1)+4*ins(a/2,b/2)
Notons que si pairs(a)
et impairs(a)
représente respectivement les nombres obtenus par la concaténation des bits pairs et impairs de a (le bit de poids faible est selon la convention informatique usuelle le bit 0, c'est à dire pair), alors pour tout entier a, a= impairs(a)\pairs(a)
On définit ainsi les fonctions pairs et impairs :
pairs(b)= (b<=0)?0:(b%2)+pairs(b/4)*2
impairs(a)= (a<=1)?0:((a/2)%2)+impairs(a/4)*2
Par exemple pairs(11)=1, impairs(11)=3 parce que
On remarquera que pour tout a = 0\pairs(a)+ impairs(a)\0
k\0
0\k
et l'encadrement :
pairs(x) <= 2**(floor(log2(x))/2+1)-1
pairs(x)> >= (2**(floor(log2(x))/2))* ((floor(log2(x))+1)%2)
si on pose
1,1,2,2,3,3,4,2,3,3,4,4,5,5,6,4,5,5,6,6,7,7,8,6,7,7,8,8,9,9
En fait
et
k=4; p[1:1200] ppi(x), 2**k*ppi(x/4**k), 2**k*ppi(x/4**k)+2**(k+1)-2
et aussi,
ppi(n) = ppi(n) = (n<2)?n: 2*ppi(n/4) + (n%2 + n%4)/2 La fonction
m42(x) = (n%2 + n%4)/2est périodique de période 4 et ses valeurs successives pour x%4 sont 0,1,1,2. cf https://oeis.org/A140081 Elle peut aussi s'écrire
floor(x) - floor(x/2) - 2*floor(x/4)`
Les minima locaux de 2**floor(log(x)/log(4.))
On pose pilog4(x) = 2**floor(log(x)/log(4.))
La fonction gnuplot suivante affiche les bits de n : Attention, ici la division des entiers est euclidienne, en javascript il faudra utiliser la fonction floor
, et en gnuplot .
est la concaténation de chaines, &
est le AND bit par bit (bitwise AND)
bits(n) = (n==0)?"0":(n==1)?"1":bits(n/2).bits(n&1)
Enfin a@b
représente la multiplication binaire sans retenue, c'est à dire en faisant le XOR et non l'addition des résultats partiels décalés. C'est aussi la multiplication dans le corps de Galois GF[2]
.
@
est commutative et associative, 1 est l'élément neutre.
avec gnuplot :
mul(a,b)= (b<2)?(b&1)*a:((b&1)*a)^(mul(a,b/2)*2)
Par exemple mul(554,655) = 351878
Notons la distributivité de @
et du XOR ^
:
(a ^ b) @ c = (a@c) ^ (b@c)
(a^b)@(a^b) = a@a ^ b@b
analogue à (a^b)@(c^d) = a@c ^ a@d ^ b@c ^ b@d
analogue à On remarque aussi que 2@b = 2b et 3@b = b ^ 2b
; par exemple 3@31 = 33
R(a,b)=(a*b)-(a@b)
est le vecteur des bits de la retenue dans la multiplication binaire de a et b.
0\a = a@a
: insertion de 0\1911
= a\0 = 2*(0\a) = 2a@a
2(1\x) = x\1 +3
0\x = (x\1)/2
1\x = 0\x + 2
(x\2)@(x\2) = (1\x)/4 = (x\1)/8
a\a = g(a\0) = 3(a@a) = 3(0\a)
: dédoublement des bits.25 = 1 1 0 0 1,
0\25 = 101000001 // 321 = 25 en base sqrt(2) ou 25@25
25\0 = 1010000010 // 642 = 2* 0\25
1\25 = 101000011 // 323
25\1 = 1010000011 // 643 = 25\0+1
25\25 = 1111000011 // 963, dédoublement des bits
Ces nombres n\n
sont aussi ceux qui s'écrivent en base 4 avec uniquement les chiffres 0 et 3, ce qui est logique car les nombres n@n
sont ceux qui s'écrivent en base 4 avec uniquement des 0 et des 1
ig(a\a) = a\0 = 2*(a@a)
Enfin
(a\b)^(b\a) = (a^b)\(a^b)
(a\b)^(b\a) = g((a^b)\0) = g(a\0)^(b\0))
Remarquons aussi que
Trois propriétés curieuses :
On a bien sûr
a\b = a\0 + 0\b
a\b + c\d = a\d + c\b
a\b ...a b a b
+ c\d ...c d c d
=
a\d ...a d a d
+ c\b ...c b c b
0\b + a\c = a\b + c@c = a\b + 0\c
a\a = 3(a@a)
,a\a + 0\a = 4*a@a
et donca\a + a\0 = 5*a@a
(x+y)\0 = ((x+y)\(x+y))*2/3
n\0 = (n\n)*2/3 = ig(n\n)
Mais
3*(a\0) = 2*(a\a)
et 3 * (0\a) = (a\a)
comme nous l'avons déjà vu.On a encore :
a\b = 2(a@a) + b@b)
, décomposition unique de a\b en bits pairs et impairs0\a + 0\b = (a&b)\(a^b)
pairs(0\x + 0\y) = x^y
impairs(0\x + 0\y) = x&y
J'ai trouvé les relations surprenantes suivantes :
(a\0)*(0\a) = (a\0)**2 /2 = 2*(0\a)**2
puisque a\0 = 2*(0\a) = 2a@a
(a\b)*(b\a) = 5*(0\a)*(0\b) + 2*(0\a)**2 + 2*(0\b)**2
(a\b)*(c\d) = (a\0)*(0\d) + (a\0)*(c\0) + (0\b)*(0\d) + (0\b)*(c\0)
(a\0)*(0\d + c\0) + (0\b)*(0\d + c\0)
(a\0 + 0\b) * (0\d + c\0)
ce qui est évident. Bof...(a\b)*(c\d) = b@b * d@d + 2*( a@a * d@d + c@c * b@b ) + 4* a@a * c@c
(2a@a + b@b) * (2c@c + d@d)
ce qui est tout aussi trivial...Quels sont les nombres de cette forme a@a * b@b
?
(a*b - a@b)/2 \ a@b = a@a * b@b
pairs(a@a * b@b) = a@b
impairs(a@a * b@b) = (a*b - a@b)/2
qui est la moitié de la retenue dans la multiplication de a par b, donc :a*b = a@b + 2*impairs(a@a * b@b)
a@a * b@b = ((a*b - a@b)/2)\(a@b)
enfin
(a*b)\(c*d) = (a*b)\b + a\(c*d) - a\b
intéressant(a*b)\(c*d) = (a*b)\a + b\(c*d) - b\a
par symétrie(a*b)\c = (a*b)\b + a\c - a\b = (a*b)\a + b\c - b\a
qui est une conséquence de a\b + c\d = a\d + c\b
donc a\b = a\d + c\b - c\d
remarquons aussi que si
Si g(x)=x^(x/2)
, où le XOR ^
est parfois noté
et si
pairs(g(a)) = g(pairs(ig(a))
impairs(g(a)) = g(impairs(ig(a))
soit la fonction swap(x)=ins(pairs(x),impairs(x))
Cette fonction échange les bits pairs et impairs.
La fonction
et, pour tout
Enfin,
#A_voir : des fonctions qui ont un furieux air de famille
p [0:256]swap(x) - floor(x)/2, 2*floor(x)-swap(x), g(x), swap(g(x)) floor(x)+swap(x)
Soit la fonction
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|
pir(n) | 0 | 0 | 1 | 0 | 0 | 2 | 3 | 0 | 2 | 0 | 3 |
k\0
ou 0\k
c'est à dire pour n=1,2,4,5,8,10,16,17,20,21,32,34,40,42,64 = A126684
par contre
n=p\1 ou n=1\p
avec p premier. c'est à dire pour n=1,2,3,6,7,9,11,19,23,35,43,71,83 ... (séquence qui n'est pas dans OEIS)
Appelons
Tous les nombres composés sont l'image par la fonction
En effet, pour un nombre composé
Par exemple pour
On remarque que pour tout n>8,
Les maximums sont atteints pour les
0,1,3,9,21,49,105,225,465,961 qui est la séquence https://oeis.org/A274230 : "Number of holes in a sheet of paper when you fold it n times and cut off the four corners." !
mx(n)=(n%2==0)?(2**(n/2)- 1)**2:2**n+1-3*2**((n-1)/2)
n@n
et 2(n@n)
ou si l'on préfère 0\n
et n\0
Si on pose R(x)=2**floor(x)-1
, alors
pir(R(x)) = R(x/2)*R((x+1)/2)
et
pir(R(x)+1) = pir(2**x) = 0
pir(ins(x,1))= pir(ins(1,x)) = x
pir(ins(x,y)) = pir(ins(y,x)) = x*y
donc pir(ins(x,x))= x**2
donc pir(ins(g(x),g(x))) = g(x)**2
pir(g(ins(x,x))) = 0
pour tout x
pir(n**2)
vaut 0 pour n = 1,2,4,8,9,16,18,32,33,36,64,66,72,128,129,132,...
, soit https://oeis.org/A114400
et surtout
souvenons-nous que
pour tout
elle est toujours positive et progresse par bonds
Mais surtout
k=-2;plot[0:256] 2**k*(swap(pir(x))- swap(2**k*pir(x))
est périodique de période 16 et prend pour x=0 à 15 les valeurs
0,0,0,1/2,0,0,0,3/4,0,1/4,0,3/4,0,1/4,0,1/2
pour k=-4, période 64...
p[1:512]pir(g(x))/2-pir(g(x)/2)
étrange... la fonction vaut zéro pour 4k et 4k+3. et n'oublions pas que
Ses valeurs sont très petites, et symétriques...
ça ressemble à pir(abs(impairs(x)-pairs(x)))
#TBC
Si n est pair,
J'ai remarqué que
plot [1:200] pir(2*floor(x)+1)- (2*pir(x)+(pir(4*floor(x)+3)-pir(4*floor(x)+1)-1)/2.0)
donc
et
Mais surtout
Enfin
Le meilleur pour la fin :
Donc
On notera que
On posera
idem pour
pir(x) %4 = pir(x%16) % 4
x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
pir(x) mod 4 | 0 | 0 | 0 | 1 | 0 | 0 | 2 | 3 | 0 | 2 | 0 | 3 | 0 | 2 | 2 | 1 | 0 |
par contre
pir(x)=4k
ssi
pir(x)=4k+1
ssi
pir(x)=4k+2
ssi
pir(x)=4k+3
ssi
enfin,
On prend n=291 = 3*97
, donc
ou encore
On pose
donc
mais puisque
donc
On pose
(on aurait pu remarquer que
On pose
on note que
On pose
On pose
Or, en regardant dans la table x pour de petites valeurs de pir(x) on remarque que
Donc
On cherche donc le plus petit nombre
On aurait pu poser
p40(x)=0
p41(x)=2*impairs(x/4)
p42(x)=2*pairs(x/4)
p43(x)=2*ppi(x/4)+1
m42(x) = (floor(x)%4 +floor(x)%2)/2
next(x)=(x%4==0)?p40(x):(x%4==1)?p41(x):(x%4==2)?p42(x):p43(x) ### pir(x) = 4*pir(x/4)+next(x)
à la fin fin de ce processus de 'descente', on a
donc x0=4*(4*(4*4*4*5)+2)+3 = 5131
et
Donc le but du jeu consiste à calculer ces restes 1,0,0,0,2,3 "en remontant"
291 = 10203 en base 4
288 = 10200 en base 4
144 = 2100 en base 4
72 = 1020 en base 4
x0=5131 =1100023 en base 4 (nos restes)
x1=1282 = 11002 en base 4
x2= 320 = 1100 en base 4
pas concluant...
Notons que n%4 = 291%4 = 3
qui est impair,
donc il faut trouver
or 145 = 4k+1
(en regardant
ce sera le cas si
Mais il faut aussi que
reste donc
donc soit
soit
ici
donc
donc
donc
or 72=4k donc
On cherche
n est supposé être impair (291 dans notre exemple)
et même n=4k+3, donc x0%16=7,11
donc pir(x0)-1 = 16k + 6,10 = n-1
donc (pir(x0)-1)/2 = 2*pir(x1)+ppi(x1) = 145
mais ppi(x1)=2*ppi(x2)+m42(x1)
avec m42(x1) =0,1,2
donc 145= 2*pir(x1)+2*ppi(x2)+m42(x1)
m42(x1)
est donc impair, donc il vaut 1 et x1%4
= 1 ou 2,
donc x1=4*x2
ou x1=4*x2+2
144= 2*pir(x1)+2*ppi(x2)
72= pir(4*x2)+ppi(x2)
= 4k72 = 4pir(x2)+ppi(x2)
donc ppi(x2)=4k=4ppi(x3)+m42(x2)
m42(x2)
est donc pair et donc il vaut 0 ou 2 et x2%4
= 0 ou 3
x2=4k
alors 72=16pir(x3)+2*ppi(x3)
36=8pir(x3)+ppi(x3)
x2=4k+3
.alors 72= 4pir(x3+2)+2*ppi(x3)+3
impossible144= 2*pir(4*x2+2)+2*pairs(x2)
= 4k72= pir(4*x2+2)+pairs(x2)
= 4*pir(x3+2)+pairs(x2)
pairs(x)%4
)pairs(x2) = 2*pairs(x3)
donc72 = 4*pir(x3+2)+2*pairs(x3)
donc 36 = 2*pir(x3+2)+pairs(x3)
2*pir(x3+2)+pairs(x3)=36
donne x3=80j'ai étudié
le ratio (quand il existe) r oscille entre 2 et 3. Il vaut exactement 2 si n est pair.
pour n impair, il semble être plus ou moins périodique lorsqu'on compare r(n) et r(4n)
Par contre r(x) = x/(pir(x)+1)
est plus intéressant :
Le ratio
Il vaut
En cherchant
Nous créons donc r2(x)=(pir(x)==0)?0:r(x)
Les "paires de ski" qui apparaissent, c'est à dire les valeurs de r2(x)
supérieures à 2**(((ilog2(x)+1)/2)-1))
pour
Pour éliminer ces "skis", nous prenons r3(x)=(pir(x)< 2**(ilog2(x)/2)+1)?0:r(x)
en fait en prenant r3(x)=(pir(x)< 2**(ilog2(x)/1.5)+1)?0:r(x)
on a presque tous les ratios
r(x) = x/(pir(x)+1)
donc pir(x) = x/r(x)-1
et x=r(x)*(pir(x)+1)
Mais r(x) est quasi autosimilaire, donc
????
r3(5131)=17.5719
et r3(5131)*292=5131
mais r(5131/2.0)=17.693
...
Partant de n=291, on a r(n)=3.38372093023256
c'est à dire
Or
??????????
#TBC
plot [1:2048] r2(x), 2**floor(log2(x)+floor(4*log2(log2(x)+1))-1)/floor(x)/128
plot [1:2064] log2(r2(x)+1)/ (log2(x)), log2(log2(2.0*r2(x)+1))/8
plot [3:3040] log2(r2(x)+1)/ (log2(x)), log2(2*log2(1.0*r2(x)+1))/10 + 1/log2(log2(x+1))-0.308944
notre estimation est un peu basse pour les x légèrement supérieurs aux 2**k et 2**k+2**(k-2)
ICI #TBC
rr(x)=log2(r3(x)+1)/ (log2(x))- log2(2*log2(1.5*r3(x)+1))/7+0.243838-exp(-x/500-2); plot [20:3000] rr(x)
???
On peut donc "renormaliser" cette fonction pour que les maxima soit égaux à 1.
Mais attention,
plot[16:2048] pir(x)/(floor(x+1)+0.0) / mx(ilog2(x+1)) * (2**ilog2(x+1)+0.0)
(voir la définition de mx() plus haut)
Attention, pour de petits x les maxima ne sont pas exactement atteints en
en posant rr(x)= pir(x)/(floor(x+1)+0.0) / mx(ilog2(x+1)) * (2**ilog2(x+1)+0.0)
on a
rr(x)= pir(x)/(floor(x+1)+0.0) / mx(ilog2(x+1)) * (2**ilog2(x+1)+0.0)
Et au fait, pourquoi ne pas "renormaliser" pir(x) lui même ?
plot[20:2048] pir(x)/(mx(ilog2(x)+1)+0.0)
:
soit pr(x)= pir(x)/(mx(ilog2(x)+1)+0.0)
Cette fonction faut 1 pour
alors plot[2:2048] pr(2*floor(x))- pr(floor(x)), pr(2*floor(x)+1)- pr(floor(x))
sont très proche de zero. :
On pose alors xr(x)= pir(x)*(1.+pr(x))/2
"pir(x) renormalisé"
Attention, si pir(n)=0 alors xr(n) vaut 0 également.
on constate que xr(291) = 50.2688172043011
et xr(5131) = 150.79190101237
soit un ratio de 2.99971 !!
en fait 5131/2= 2565, xr(5131/2) = 149.224
,
5131/4= 1282, xr(5131/4)*4 = 98.359
, un ratio de 1,5...
pr(5131)= 0.0363704536932883
~93/2667
pr(291) = 0.182795698924731
~ 17/93
pr(291)/pr(5131) = 5.02593947455936 ~ 17/93
à
or 5131=17*291+2*(93-1) ....
???
essayons avec 469=7x67 ; pr(469)=0.53333333333333 = 8/15
8x469+2x(15-1) = 3780... NOK en revanche 469x8+17x23 = 4143 et pir(4143)=469
On aussi xr(469)=190.13333 = 2852/15 ??
????
ICI 28/08 #TBC
Or, on peut minorer
plot[4:200] pir(x),2*pir(x/2),4*pir(x/4), 8*pir(x/8)
Peut-on trouver des majorants ? bien sûr !
pour k>0 donné, on posera
down(x,k)=pir(floor(x/2**k))*2**k
(minorants)
up(x,k) = pir(floor(x/2**k)*2**k+2**k-1)
(majorants)
et pour tout
vu que
En généralisant, vu que
print [1:200] 2**(k+1)*ppi(x/4**k) , 2*ppi(x) , 2**(k+1)*ppi(x/4**k)+2**(k+2)-4
On pose ppir(x) = 2pir(x)+ppi(x)
cherchons à factoriser
on cherche
on suppose que x < 2n.
...
On trouve
et
Bon en fait c'est pas si simple, il n'est pas vrai que le
Supposons qu'on l'ait trouvé, donc
et donc
Il est remarquable que si on pose
ça fait penser ) un battement de signaux sinusoïdaux... ou à Mandelbrot...
en fait pour tout
plot [0:255] f(x/2)*2-f(x),(pairs((x/2))+floor(x)%2)*(-1)**floor(x)
plot [0:255] (f(x)-f(x/2)*2)*((floor(x)%2==0)?-1:1), pairs((x/2))+(floor(x)%2)
et même, pour tout k positif,
ou
Donc
#TBC
16:
plot [0:256] pir(floor(x)*16+0)-pir(floor(x)*16), 0
plot [0:256] pir(floor(x)*16+1)-pir(floor(x)*16), impairs(x)*4
plot [0:256] pir(floor(x)*16+2)-pir(floor(x)*16), pairs(x)*4
plot [0:256] pir(floor(x)*16+3)-pir(floor(x)*16), pairs(x)*4 + impairs(x)*4+1
plot [0:256] pir(floor(x)*16+4)-pir(floor(x)*16), impairs(x)*8
plot [0:256] pir(floor(x)*16+5)-pir(floor(x)*16), impairs(x)*12
plot [0:256] pir(floor(x)*16+6)-pir(floor(x)*16), pairs(x)*4+ impairs(x)*8+2
plot [0:256] pir(floor(x)*16+7)-pir(floor(x)*16), pairs(x)*4+impairs(x)*12+3
plot [0:256] pir(floor(x)*16+8)-pir(floor(x)*16), pairs(x)*8
plot [0:256] pir(floor(x)*16+11)-pir(floor(x)*16), pairs(x)*12 + impairs(x)*4+3
plot [0:128] pir(floor(x)*16+15)-pir(floor(x)*16), pairs(x)*12 + impairs(x)*12+8
k=3;r=1;plot [1:256] pir(2**k*floor(x)+r)-2**k*pir(x) - (2**(k/2+1)*impairs(x)*impairs(r)+2**(k/2)*pairs(x)*pairs(r)+pairs(r)*impairs(r))
en fait la formule générale est, pour
Enfin, si
prenons
(n-1)/2=145 est impair;
en fait n=2x145+1=71x4+3= 368+3 = 1816+3 = 9x32+3 (k=5)
choisissons k=5 et essayons tous les x entre 1 et 18
Nous constatons que pir(15)=n/32. =9
Nous ignorons encore r, mais puisque k est impair,
On pose
d1(x,k,r)=2**(k/2+1)*impairs(x)*impairs(r) + 2**(k/2)*pairs(x)*pairs(r) + pairs(r)*impairs(r)
d2(x,k,r)=2**(k/2)*pairs(x)*impairs(r) + 2**(k/2)*impairs(x)*pairs(r) + pairs(r)*impairs(r)
d(x,k,r)=(k%2==0)?d2(x,k,r):d1(x,k,r)
on essaye tous les r entre 1 et 32... finalement
pour k=5, r=11, y=160, 2**k*pir(y)+d(y,k,r) =n
idem pour k=7, r= 11, y=40 et
k=9, r=11, y=10 et
k=10, r=11,y =5
k=10;r=x%(2**k); y=x/2**k; pr k,r,y, 2**k*pir(y)+d(y,k,r), 2**k*y+r
qui donne 10 11 5 291 5131
k=11, r=1035, y=2 !
Et bien sûr, pour toutes ces valeurs,
Le problème est donc de trouver les bons k,r et y...
Or nous avions trouvé
donc le x cherché est vaut
Donc
donc
Or, si on se souvient que ce nombre est de la forme
De plus,
Pas simple... Peut être en le faisant à l'envers ?
Nous savons que pir(15)=n/32=9
et pir(5131)=n=291
5131=2*2565+1
donc 2*pir(2565)+pairs(2565)=n
et pairs(2565)=3
2565=2*1282+1
donc 2*pir(1282)+pairs(1282)=pir(2565)=144
et pairs(1282)=48
pir(1282) = 2*pir(641)
641=320*2+1
2*pir(320)+pairs(320)=pir(641)=24
et pairs(320)=24
pir(320)=0 = floor(n/2**9
(et 9 est le plus petit nombre)
En remontant...
il faut essayer tous les k
entre 1 et 2**9
(en fait uniquement ceux qui ont des pairs(k)
différents donc 31 possibilités) et les prendre comme "racine". je ne teste l'idée que pour k1=320, et donc pairs(k1)=24
Donc l'essai suivant (N°1) sera 2k1+1=320*2+1=641
et
pour l'essai 2 nous prenons soit k2=1282, soit 1283
pir(1282)=48
et pir(1283)=49
Aucun des deux n'est proche d'un n/2**r
donc on continue
k3=2*1282+1=2565
et version 1 :
cf factopir.js (Fichier sur D)(lien privé)dans mon ordi... (version 1, qui utilise les majorations et minorations de pir(x))
x=4k+3
etn= pir(x)=4*pir(x/4)+2*ppi(x/4)+1
ppi(x/4) %4 = 0
donc x/4 = 16k+0,1,7,11,12 ??si n=4k+2....
Vu que
3,6,12,24,72,264,1032,4104,16392,65544,262152
8,9,12,13,24,25,28,29
est A131864 "la suite telle des nombres n tels qu'une certaine fonction z(n) a une partie imaginaire <0".... oops...
et aussi
pour
pour les n impairs, inv(n) est plus compliquée...
mais
plot [2:200] inv(2*floor(x)+1), ins(x,1)*2
inv(2*floor(x)+1) = ins(x,1)*2+1
pour beaucoup de valeurs 1,2,3,5,6,8,9,11,14,15,18,20,21,23
...
et ins(x/3,0)*2
pour beaucoup d'autres
#TBC 23/08
Si
donc
c'est à dire
ou encore
donc
voir encadrement de 2pir(x)+ppi(x)
or
#TBC ICI 06/09/224
que vaut inv(2**k+x) ? et pir(3*2*k+n) ?
si n < 2**k
pairs(3*2**k+n) = 2**ceil(k/2.)+pairs(n)
impairs(3*2**k+n) = 2**floor(k/2.)+pairs(n)
donc pir(3*2**k+n) = 2**k + pairs(n)*2**floor(k/2.) + impairs(n)*2**ceil(k/2.) + pir(n)
si n=1
, pir(3*2**k+1) = 2**k + 2*floor(k/2.)
???
Mais si
alors pairs(3*(2**a+2**b)) = 2**((a+1)/2)+2**((b+1)/2)
sauf si a=2k, b=2k+1
ou a=2k+1, b=2k
(donc OK si a=2k+1,b=2k+2
et impairs(3*(2**a+2**b)) = 2**(a/2)+2**(b/2)
sauf si a=b
ou a=2k, b=2k-1
ou a=2k-1, b=2k
Donc pir(3*(2**a+2**b) =
????
ICI 02/09/2024 #TBC
En fait on peut définir
insf(n,p)=ins(p,n/p)
inv(x)=insf(floor(x),facto(x))
ou encore inv(x)=ins(facto(x),x/facto(x)
Où facto(x) renvoie le plus petit facteur premier de x, et 1 pour les nombres premiers.
inv(0)=1, inv(1)=3, inv(2)=6, inv(3)=7, inv(4)=12, inv(5)=19
et on a
Si
Si
Si
SI on se souvient que
Et aussi
Soit n\1
et 1\n
L'espoir est que, si on peut trouver un tel
Rappelons-nous que si l'on sait factoriser
insf(n,p)=ins(p,n/p)
inv2(x)=insf(floor(x),facto(x))
pr inv2(291) # 5131
soit inv(n)
la fonction qui retourne le plus petit (ou presque..)
inv(0) = 0
inv(1) = 3
inv(2) = 6
inv(3) = 7
inv(4) = 12
inv(5) = 19
inv(6) = 13
inv(7) = 23
inv(8) = 24
inv(9) = 15
et la suite 0,3,6,7,12,19,13,23,24,15
n'est bien sûr (?) pas dans OEIS...
Dans la liste ci-dessous les nombres entre
n@n
et 2(n@n)
ou si l'on préfère 0\n
et n\0
(cf propriétés de $pir(n)$)
... les 2 derniers nombres de chaque liste donnent 1xn
les premiers termes donnent la suite
pour n pair, la sous-suite 11
?
pour n impair (le cas intéressant), on a la sous-suite
Si
Mais si
0,2,4,18,36,144,288,572,578,1144,1156,1168
Avec gnuplot :
ok(x,k,r)=(r<0)?-1:(pir(k*x+r)==x)?0:ok(x,k,r-1)
f(x)=ok(x,k,k-1)
zeros(a,b)=(a>b)?"":(f(a)==0)?"".a.",".zeros(a+1,(a+b)/2).zeros((a+b)/2+1,b):zeros(a+1,(a+b)/2).zeros((a+b)/2+1,b)
k=11 #par exemple
print zeros(0,10000)
Les autres modulo ne sont pas périodiques bien qu'il y ait des sections identiques dans le graphe...
Soit
Il existe plusieurs de ces fonctions, on prendra
pour 1,3,6,7,12,19,13,23,24,15,25,71,28
or x=3,6,12,24,48,96...
110..0
et via la fonction 1
tombe dans l'escarcelle de ceil(k/2.)
, l'autre dans la besace de floor(k/2.)
.
donc
j'ai découvert que inv(x)
et swap(inv(x)/2)
sont très proches pour des nombres qui ont de petits diviseurs : (image en échelle logarithmique)
Les valeurs successives (pour 2,2,2,2,6,2,6,2,6,8,6,2,6,2,6,8,6,2,6,2,6,8,6,2,6,26...
1,2,4,5,8,10,16,17,20,21,32,34,40,42...
qui est https://oeis.org/A126684, soit si k\0
ou 0\k
ce qui implique pir(x)=0
il y a quelque chose de bizarre dans
plot [0:1024][1:1024] inv(pir(x)), min(x,swap(x))
en effet ces valeurs sont égales pour beaucoup de x :
majoration :
2,3,6,7,18,19,22,23,66,67,70,71,82,83,86,87,258
minoration :
il semble que inv(x) > 1.6*2**(ilog2(x))
?????
ou bien inv(x) > x
?
les maxima locaux de
"l'étage 2 juste en dessous" est
en fait inv(x) n'est jamais proche de ins(1,x)/3
"l'étage 3 juste en dessous" est
et ins(1,291/3)+8 = inv(291) = 5131
en fait on utilisé les fonctions
h1(x)=(abs(inv(x)-ins(1,x))<100)?inv(x)-ins(1,x):-1
apériodique, rend les valeurs 0 et -1
h2(x)=(abs(inv(x)-ins(1,x/2))<100)?inv(x)-ins(1,x/2):-1
périodique (période 2) rend les valeurs 6 et -1 sauf pour 11,13,21,25,27,51,57,63
h3(x)=(abs(inv(x)-ins(1,x/3))<100)?inv(x)-ins(1,x/3):-1
périodique, prend les valeurs 8 et -1 sauf pour un certain nombre de petites valeurs (<63)
h4(x)=(abs(inv(x)-ins(1,x/4))<100)?inv(x)-ins(1,x/4):-1
apériodique, rend la valeur -1 pour tous les x >186, sauf pour 245 ?
h5(x)=(abs(inv(x)-ins(1,x/5))<100)?inv(x)-ins(1,x/5):-1
périodique, rend les valeurs -1 et 32 pour x>94 sauf 119 et 133
h6(x)=(abs(inv(x)-ins(1,x/6))<50)?inv(x)-ins(1,x/6):-1
apériodique
h7(x)=(abs(inv(x)-ins(1,x/7))<50)?inv(x)-ins(1,x/7):-1
périodique, rend les valeurs -1 et 40
res(k)=(k<=1)?0:(k==2)?6:(k==3)?8:(k==4)?0:(k==5)?32:(k==6)?0:40
inv2(x,k)=ins(1,x/k)+res(k)
divise(x,d)=(d!=x && d != 1 && x%d==0)
ok(x,k)=divise(x,pairs(inv2(x,k)))?pairs(inv2(x,k)):-1
test(x,k)=(k>7)?"echec":ok(x,k)>0?ok(x,k):test(x,k+1)
fact(x)=test(x,1)
fact(291) # 97
fact(13) # echec
On n'a pas fait mieux que le crible d'Erathotène ?? sauf que les étapes suivant 7 ne rendent que -1...
a priori
intéressant :
Cette fonction est quasiment
en fait,
C'est à dire la somme des deux diviseurs de
En effet, si
donc
plot [1:255] (inv(4*floor(x)+3)-(inv(4*floor(x)+1))-1)
soit la fonction
Si
Si on veut factoriser
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
c(n) | 4 | 6 | 6 | 9 | 8 | 10 | 12 | 15 | 8 | 12 | 10 | 15 |
...of course (?) pas dans OEIS.
Comme pour
Les 20 premières valeurs de c(x) sont
4,6,6,9,8,10,12,15,8,12,10,15,16,20,20,25,12,14,18,21,16
Contrairement à
6,8,8,12,12,20,20,36,36,68,68,132,132,260,260 (pas dans OEIS),
cependant
et les maxima (en
6,9,15,25,45,81,153,289,561,1089,2145,4225,8385,16641,3315
pas dans OEIS non plus, mais pour les indices pairs on a
En fait pairs(2**k-1) = 2**((k+1)/2)-1
et
impairs(2**k-1)=2**(k/2)-1
Donc nos maximas sont les 2**((k+3)/2) + 2**((k/2+1))+mx(k)
borne sup :
p[0:1024] c(x), 2**((ilog2(x)+3)/2) + 2**((ilog2(x)/2+2))+mx(ilog2(x)+1)
c(x) est pair pour x=4k+0,1,2
c(x) est impair pour x =4k+3
c(2n) est toujours pair
c(2n+1) est pair ssi n est pair
j'ai trouvé les relations suivantes :
function pairs(n) {
// pairs(b)= (b<=0)?0:(b%2)+pairs(b/4)*2
if (n==0) return 0;
if (n==1) return 1;
return n%2+pairs(Math.floor(n/4))*2;
}
function c(n) {
if (n==0) return 4;
if (n==1) return 6;
if (n%2 ==1) {
let m = (n-1)/2;
return c(m)+c(n-1)/2;
}
// n pair
return 2*c(n/2)-2*pairs(n/2)-4;
}
console.log(c(2),c(3),c(4),c(5),c(6),c(7),c(8));
on pose invc(x)=ins(facto(x)-2, x/facto(x)-2)
ça ressemble beaucoup à inv(x) mais c'est différent
cette différence vaut 0 pour tous les nombres pairs, et 3 pour presque tous les impairs, mais parfois 15,51,195, 207,255...
C'est plus compliqué...
n=291=3*97, p=3, q=97, x=ins(p-2, q-2)=4439, c(x)=n
n/2=2219, c(2219)*2=294
n/4=72, c(72)*4 = 160
donc pas génial
mais n=2*145+1
donc
ICI 27/08
p[200:5160] c(x)- c(2*floor(x)+0)/2, c(x)- c(2*floor(x)+1)/2
c20(x)=c(x)- c(2*floor(x)+0)/2
p[200:5160] c20(x), c20(x/4)*2
-> oscille entre -1 et -2
c21(x)=c(x)- c(2*floor(x)+1)/2
p[200:5160] c21(x), c2(x/4)*2
-> oscille entre 0, -1 et -2
en fait au lieu d'utiliser les fonctions pairs
et impairs
on pourrait multiplier des groupes de 2,4, 8 bits etc.
ABCDEFGHILKLMNOP -> pir -> ACEGIKMO * BDFHJLNP
-> pir2 -> ABEFIJMN * CDGHKLOP
-> pir4 -> ABCDIJKL * EFGHMNOP
-> pir8 -> ABCDEFGH * IJKLMNOP
x | 8 | 9 | 10 | 11 | 14 | 16 | 20 | 21 | 24 | 32 | 33 |
---|---|---|---|---|---|---|---|---|---|---|---|
y | 4 | 6 | 5 | 7 | 13 | 6,9 | 12 | 18 | 22 | 6,9,16 | 18,21 |
Pas très clair...
Une fonction qui compte les doublons
dd(x,y)=(y<=1)?0:(c(floor(x))==c(floor(y)))?1+dd(x,y-1):dd(x,y-1)
doublons(x)=dd(floor(x),floor(x)-1)
La conjecture de Dubner suppose que tous les nombres pairs supérieurs à 4210 sont somme de deux nombres premiers ayant un jumeau. Elle implique donc twin primes et Goldbach.
Comme
p est premier ssi
or si p est impair, inv(p)%4=3
en fait, x est premier ssi inv(x)/(ins(0,x)+0.0) > 1
et même > 0.25
!!!!
#TBC ICI 07/09
Liste des fonctions utilisées dans ce document :
bits(n)=bits1(floor(n))." "
bits1(n) = (n==0)?"0":(n==1)?"1":bits1(n/2).bits1(n&1)
ins(a,b) = (a==0&&b==0)?0:(b&1)+2*(a&1)+4*ins(a/2,b/2)
pairs(b)= (b<=0)?0:(b%2)+pairs(b/4)*2
impairs(a)= (a<=1)?0:((a/2)%2)+impairs(a/4)*2
ppi(x)=pairs(x)+impairs(x)
mul(a,b)= (b<2)?(b&1)*a:((b&1)*a)^(mul(a,b/2)*2)
ilog2(x)=floor(log(x)/log(2.))
pilog2(x) = 2**floor(log(x)/log(2.))
pilog4(x) = 2**floor(log(x)/log(4.))
pir(n)=pairs(n)*impairs(n)
mx(n)=(n%2==0)?(2**(n/2)- 1)**2:2**n+1-3*2**((n-1)/2)
facto1(d,n)=(n%d==0)?d:(d*d>n)?1:facto1(nextprime1(d),n)
facto2(n) =(n<=1)?1:(n%2==0&&n!=2)?2:(n%3==0&&n!=3)?3:(n%5==0&&n!=5)?5:(n<49)?1:facto1(7,n)
facto(n) =facto2(floor(n))
nextprime1(n)=(facto2(n+2)==1)?n+2:nextprime1(n+2)
nextprime2(n)=(n<2)?2:(n%2==0)?nextprime1(n-1):nextprime1(n)
nextprime(n) =nextprime2(floor(n))
insf(n,p)=ins(p,n/p)
inv(x)=insf(floor(x),facto(x))
R(x)=2**floor(x)-1
swap(x)=ins(pairs(x),impairs(x))
c(x)=(pairs(x)+2)*(impairs(x)+2)
invc(x)=ins(facto(x)-2, x/facto(x)-2)
page créée le 18/03/2025 à 15:09
modifiée le 25/05/2025 à 12:05
Commentaires (0) :
Page :Ajouter un commentaire (pas besoin de s'enregistrer)
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !Ah oui : le bbcode et le html genre <br>, <a href=...>, <b>b etc. ne fonctionnent pas dans les commentaires. C'est voulu.