On va utiliser les fonctions unaires et binaires pour construire une fonction f qui donnera, après un certain nombre d'itérations, un diviseur premier de n. (pas sûr que ça marche)

cf factorisation par insertion de bits

Supposons que l'on veuille factoriser .
On le décompose en n=p\q donc n=2p@p + q@q
On factorise p=a*b et q=c*d donc
n = ab\cd = (ab)\b + a\(cd) - a\b = p\b + a\q - a\b
n + a\b = p\b + a\q = p\q + a\b
donc n = p\q bof...
Mais on peut aussi factoriser p et q dans GF[2] : p=r@s et q=t@u
De même le nombre f= est sans doute important

Peut-on, si n est composé, et à partir de p,q,a,b,c,d,f,r,s,t,u, des constantes 1,2,3,5 et des opérations unaires **2,g,ig,facto,pairs,impairs et binaires \,/,^,+,-,*,@, fabriquer deux nombres et tels que n=A*B avec ?

Par exemple pour n=7*11 = 77 = 2\11 on a déjà un diviseur !
pour n=11*23 = 253 = 14\15 on a ig(14)=11 mais c'est sans doute une coïncidence...
pour n=101*151 = 15251 = 121\85 on a 101=ig(85)+1 encore une coïncidence...

Posons les deux multiplications "enchevêtrées" p=a*b et q=c*d dont le résultat est n : (on choisira et ) et on remplace les 0 par des blancs pour plus de lisibilité

Cette multiplication serait ordinaire si a et c étaient égaux... mais on peut prendre les lignes deux par deux : ainsi la somme des deux lignes supérieures est :
0 si d0 = b0 = 0
0\c si d0=1 et b0=0
a\0 si d0=0 et b0=1
a\c si d0 = b0 = 1
(en fait comme a,b,c, et d sont impairs c'est le dernier cas qui est vrai pour les deux premieres lignes, on a donc :

On peut définir de même les sommes de chaque couple de lignes.
L'idée et de modifier progressivement les lignes et les multiplicandes pour faire converger les lignes vers une "moyenne" (qui pourrait être a^c ? ou pas ?)

Attention, les retenues "sautent" deux colonnes : par exemple la retenue de a1b0*a0b1 (colonne p1) se retrouve au sommet de la colonne p2. Mais il suffit, au cas où c1+c0<=2, d'ajouter un "1" dans la colonne q1 ou de remplacer c0 ou c1 par #TBC
Il est aussi possible de prendre un bit sur 3, ou sur 4, et ainsi de suite.

Si n est un entier naturel composé (non premier),
et si on le décompose en bits pairs et impairs parn = p\q, que l'on factorise: p=a*b et q=c*d,
si on extrait de n d'autres constantes dépendantes de n comme
n1s2 = (=(n-1)/2)) et sn = floor(sqrt(n))
ou encore ffsn = floor(frac(sqrt(floor(x)))*sqrt(floor(x)))
alors peut-on,
à partir des constantes dépendantantes a,b,c,d, n1s2, sn, ffsn, etc.,
des constantes "indépendantes" 1,2,3,5 et des opérations :
unaires carré,g,ig,facto,pairs,impairs,floorSqrt,
binaires \,/,^,+,-,*,@ A VOIR : max et min ?
fabriquer deux nombres A et B tels que n=A*B avec A>=2 ?
(\ est l'insertion des bits, @ la multiplication sans retenue)

On va générer successivement toutes les fonctions possibles de complexité croissante, et tester chacune d'elle sur quelques exemples.

voir test facto par insertion (Fichier sur D)(lien privé)

Soit la fonction "plus grand facteur premier", cf. https://oeis.org/wiki/Greatest_prime_factor_of_n.
Si est premier, , et par convention

Dans la suite désigné l'itération de f, k fois, avec et .

On suppose qu'il existe une fonction qui à partir d'un nombre dont l'écriture binaire mesure bits, renvoie un autre nombre , et telle que, pout tout :

Notons que si est premier, , mais aussi

La fonction serait ainsi un peu comme la fonction de La conjecture de Collatz, à ceci près qu'elle aurait une infinité de boucles au lieu de . Elle pourrait aussi ressembler aux suites aliquotes (cf https://math.dartmouth.edu/~carlp/upintconf.pdf) et https://www.aliquot.de/aliquote.htm

Ce qui serait sympa, c'est que si l'écriture binaire de mesure  bits, alors soit majoré par un polynôme en , et donc le problème de la factorisation serait dans P !

Si n est le carré (ou en fait une puissance quelconque) d'un nombre premier , alors

La fonction f ne peut pas être constante, et elle décroît parfois (lorsque n'est pas premier), donc elle doit aussi croître parfois. En fait, en partant d'un nombre premier :

#TBC...