Indicatrice d'Euler

Méthode brutale: pour résoudre $\phi(n)=a$, il suffit de tester tous les $n$ impairs avec $n\le a+1$.
les solutions sont les $n$ et les $2n$, avec les $n$ qu'on a trouvés.

Edit: petite bêtise corrigée.

bon je fais en direct pour $a=30$. Les premiers jusqu'à $a+1$ sont $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31$, je veux $p-1\mid 30$ il y a $p=2,3,7,11,31$. Ensuite les $p^k - p^{k-1}$ max sont $2^2-2^1$, $3^2-3$, $7-1$, $11-1$, $31-1$, mon produit cartésien est $\{1,2^1-2^0, 2\}\times\{1,2,6\}\times\{1,6\}\times\{1,10\}\times\{1,30\}$, les penta-uplets (pentuplets?) possibles sont $(1,1,1,1,30)$, $(2^1-2^0,1,1,1,30)$, et ben c'est tout. Il n'y aurait donc que $n=31$ et $n=62$. Bon.

Je fais un autre essai avec $a=2^3 3^2 5^2 = 1800$. Bon là je vais pas faire la liste des premiers je fais plutôt la liste des diviseurs $d$ et je regarde si $d+1$ est premier, il y a $36$ diviseurs, bon faut le faire, alors les diviseurs sont ... euh bon c'est un long là à la main, mais on peut le faire. Si on y passe quelques après-midi on finira rapidement par connaître par cœur tous les nombres premiers inférieurs à $1000$... ce n'est pas Gauss qui les calculait par tranche de mille entiers criblés à ses heures perdues ?

ok avec un peu d'aide je trouve 2,3,5,7,11,13,19,31,37,41,61,73,101,151,181,601,1801 comme premiers candidats, et les max sont 16-8, 27-9, 125-25, et pour tous les autres c'est juste $p-1$. Je m'aperçois qu'un tableau comme ceci facilite :

1,     1,   2,   4,   8,
1,     2,   6,  18,
1,     4,  20, 100,
1,     6
1,    10
1,    12
1,    18
1,    30
1,    36
1,    40
1,    60
1,    72
1,   100
1,   150
1,   180
1,   600
1,  1800

Toutes les façons de faire 1800 se déterminent là-dessus :
(je scanne le tableau du bas en haut)
1800, 10x180, 12x150, 2x6x150 (trois fois)
,18x100 (deux fois),30x60,6x10x30 (deux fois), et 100x18 et
à nouveau 18x100 (en deuxième ou troisième examen!)
et ça a l'air d'être tout, faut être consciencieux. Ça donne 1801 et 3602, 1991
et 3982, 1963 et 3926, 4x9x151,4x7x151,3x7x151 et son
double, 1919 et 3838, 2727 et 5454, 31x61 et son double,
7x11x31 et son double, 9x11x31 et son double, 125x19 et son double
et (après avoir revérifié, 27x125=3375 et son double

J'ai dû en rater, je trouve 1801, 3602, 1991, 3982, 1963, 3926, 5436, 4228, 3171, 6342,
1919, 3838, 2727, 5454, 1891, 3982, 2387, 4774, 3069, 6138,2375, 4750, 3375, 6750

Miracle, je vérifie avec maple, et ils ont tous bien phi(n)=1800. Bon j'avoue, j'en avais raté 4 au
premier passage.

Merci à AD pour les travaux d'embellissement !
[A ton service AD]

Pour que $\phi(n)$ ne soit pas multiple de $4$ il est nécessaire et suffisant que $n=1$ ou $n=2$ ou $n=4$ ou $n = p^b$ ou $n=2 p^b$ avec $p$ un nombre premier congru à $3$ modulo $4$ et $b$ un entier au moins $1$. Dans tous les autres cas $\phi(n)$ est un multiple de $4$.

J'ai écrit cela très vite, j'espère pas trop vite. Je relis une fois (mais j'ai ma soupe qui chauffe). Ça a l'air bon.

@Élie: connais-tu la formule $\phi(n) = \prod (p^k-p^{k-1})$ lorsque $n = \prod p^k$ ?

> restart;
> with(numtheory):
> gottinvphi := proc(a::posint)
#
# petite procédure par Gottfried 
#    v3 23 janvier 
#    v2 21 janvier
#    v1 20 janvier 2012
# pour calculer les n avec phi(n)=a
# semble fonctionner mieux que le invphi de Maple 9
# (par exemple prendre a = 1800)
# comme je ne connais rien aux entrailles
# de Maple, le code n'est en rien optimisé
# l'algorithme lui-même est certainement naïf
# j'ai juste pris quelques mesures de bon sens
# pour limiter les calculs inutiles.
#
# la liste des n n'est pas fournie dans l'ordre croissant
# utiliser sort(gottinvphi(a)) pour cela.
#
# gottinvphi nécessite numtheory pour divisors
# et utilise aussi isprime.
# 
local 	d, lesd, p, lesp, 
	tableau, tabind, soustableau, 
	lesn, nbsols, j, k, ak, pk, qk, Q, scan;
#
# sous-procédure récursive «scan» 
# qui sera utilisée
# une fois établi le «tableau»
# des constituants potentiels
#
	scan := proc(top,A,n)
	local j, w, z;
	for  j from 2 to tabind[top] by 2 do 
		w := tableau[top][j];
		if (w>A) then break fi;
		if (w=A) then 
			z := n*tableau[top][j-1];
			nbsols := nbsols+1; 
			lesn[nbsols] := z;
			if (top>1) then 
				nbsols := nbsols+1; 
				lesn[nbsols] := 2*z;
			fi;
			break;
		elif (irem(A,w,'Q')=0) then 
			if (top>1) then
				z := n*tableau[top][j-1];
				scan(top-1,Q,z)
			fi
                else break;
		fi
	od;
	if (top>1) then scan(top-1,A,n) fi
	end proc;
# fin de la sous-procédure
# 
if a = 1 then RETURN([1,2]) fi;
if type(a,odd) then RETURN([]) fi;
lesd := convert(divisors(a),list);
lesp := [];
for d in lesd do 
if isprime(d+1) then lesp := [op(lesp),d+1] fi 
od;
tableau := 'tableau'; tabind := 'tabind';
	for j from 1 to nops(lesp) do
		p := lesp[j];
		qk := p-1; pk := p; ak := a/qk; 
		soustableau := 'soustableau';
		soustableau[1] := pk;
		soustableau[2] := qk;
		k := 2;
		while true do 
			if (irem(ak,p,'Q')= 0) then
			qk := p*qk; 
			pk := p*pk;
			ak := Q;	
			k := k+1;
			soustableau[k] := pk;
			k := k+1;
			soustableau[k] := qk;
			else break fi;
		od;
		tableau[j] := eval(soustableau);
		tabind[j] := k;
	od;
nbsols := 0; lesn := 'lesn';
scan(nops(lesp),a,1); 
#
	if (nbsols = 0)	then 	
			RETURN([]) 
			else
			RETURN(convert(eval(lesn),list)) 
	fi
end proc:
# FIN DE LA PROCEDURE gottinvphi

Sur mon ordi (de 2004) où j'ai maple 9, il y a un (gros) problème avec le «invphi» comme on le voit par ces essais (*) qui comparent avec «gottinvphi»:

(*) ces essais ont été faits avec une version antérieure, beaucoup plus lente, de «gottinvphi», sur un ordi de 2004

> testinvphi(200);
            [275, 303, 375, 404, 500, 550, 606, 750]
Ce calcul a été fait par Gottfried en 0.000 secondes

            [275, 303, 375, 404, 500, 550, 606, 750]
Ce calcul a été fait par invphi en 0.030 secondes

> testinvphi(1000);
[1111, 1255, 1375, 1875, 2008, 2222, 2500, 2510, 2750, 3012, 3750]
Ce calcul a été fait par Gottfried en 0.010 secondes

[1111, 1255, 1375, 1875, 2008, 2222, 2500, 2510, 2750, 3012, 3750]
Ce calcul a été fait par invphi en 0.060 secondes

> testinvphi(1200);
[1201, 1271, 1313, 1525, 1625, 1705, 1803, 1925, 2013, 2121, 2265, 2325, 2402, 2404, 2416, 2475, 2542, 2625, 2626, 2684, 2728, 2828, 3020, 3050, 3100, 3250, 3410, 3500, 3606, 3624, 3636, 3850, 4026, 4092, 4242, 4500, 4530, 4650, 4950, 5250]
Ce calcul a été fait par Gottfried en 0.020 secondes

Warning,  computation interrupted

> debut := time(): testinvphi(1800); printf("interrompu après %.3f secondes mais ça allait durer une éternité", time()-debut);
[1801, 1891, 1919, 1963, 1991, 2375, 2387, 2727, 3069, 3171, 3375, 3602, 3782, 3838, 3926, 3982, 4228, 4750, 4774, 5436, 5454, 6138, 6342, 6750]
Ce calcul a été fait par Gottfried en 0.020 secondes

Warning,  computation interrupted
interrompu après 13.960 secondes mais ça allait durer une éternité

Clairement le invphi de mon maple 9 (sur un Mac OS X) est bogué.

Peut-être qu'un spécialiste de Maple passera par là?

EDIT; oups ma fonction inverse faisait n'importe quoi pour a=1!
EDIT2: ma procédure avait plusieurs lourdeurs, j'ai essayé d'y remédier.
EDIT3: je modifie un ou deux aspects maladroits (comme de faire des divisions) que ma remédiation avait introduits.
EDIT4: je remodifie la procédure afin de minimiser la répétition des opérations arithmétiques.
EDIT5: il y avait encore un ou deux bêtises; de plus je commence à mieux comprendre quelles structures de données maple sont plus lentes que d'autres, dans ce contexte.
EDIT5bis: décidément j'avais encore oublié un break. Bon là c'est bon.

Bonjour,

On ne comprend pas vraiment ces durées alors qu'un programme écrit en JavaScript (!!!) donne la liste pour a = 1800 en 0.033s (Firefox, PC avec un X86 à 2800MHz, normal quoi)
Même sur un vieux tarare (Pentium II à 100MHz ?) il ne met que 3.9 secondes !

Et ce programme là est en plus vraiment bourrin de chez bourrin :

pour n de a+1 au maxi par pas de 1 !!
| calcul de phi(n) par décomposition bourrine en nombres premiers
| (2 et tous les nombres de 3 à sqrt(n) de 2 en 2 sont essayés comme diviseurs !!)
| si = a, afficher

On ne peut pas faire plus "force brute" que ça !!

Maple = (td)

@ chephip: intéressant et stupéfiant! mais je ne pense pas dans ce cas que c'est Maple dans son ensemble qu'il faille (td), c'est surtout que «invphi» de mon maple v9 y est bogué, lorsqu'on lui donne certains entiers comme 1800 ou 1200. Sinon, je m'aperçois que ma procédure passe inutilement tout un tableau (qui ne change pas!) dans un appel récursif ce qui est totalement absurde (suffit de passer un indice, ce qu'elle fait d'ailleurs déjà; décidément, faut jamais travailler après 6 heures de l'après-midi, vaut mieux aller se coucher), après déjeuner je vais arranger cela. Malgré ses défauts, mon ordi qui est beaucoup plus lent que le tien (PowerPC de 2004), n'a aucun problème pour faire la liste des antécédents pour 1<a<10000 en quelques secondes, alors que le «invphi» de Maple met péniblement deux minutes (!!) pour 1<a<1000.

gottfried a écrit:

je m'aperçois que maple a (dans son paquet «numtheory») non seulement la fonction phi de Euler mais aussi une fonction invphi, qui fait exactement ce que tu veux. Je ne sais pas comment ils ont programmé cela, ni si c'est possible de le savoir

Si si, c'est possible, mais après, faut encore déchiffrer :

> print(invphi);         
proc(a)
local d, divlist, i, j;
    if not type(a, posint) then return 'procname'(args) end if;
    d := ifactors(a)[2];
    divlist := sort(map(convert, combinat[powerset]([seq(seq(op(1, d[j]), i = 1 .. op(2, d[j])), j = 1 .. nops(d))]), '`*`'));
    divlist := select(type, divlist, 'even');
    divlist := select(x -> isprime(x + 1), divlist);
    remove(has, sort(map(convert, invrec(a, divlist), '`*`')), FAIL)
end proc

merci à tous pour vos infos il y a quelque chose de spécial sur le maple 9 qui tourne sur mon ordi (les fonctions comme divisors ou isprime en tout cas fonctionnent correctement il semble).

@Guego: je vais regarder le code officiel de maple pour invphi

J'ai mis à jour mon message initial avec une procédure un peu améliorée.

@Ga? voici ce que ma procédure donne sur ton exemple

> debut := time(): gottinvphi(1800000); nops(%); time()-debut;
[2700003, 5400006, 3600004, 2250005, 4500010, 5400012, 3600008, 1980011, 
                    etc... etc ...
 4265625, 8531250, 5687500, 7312500, 8662500, 7425000, 7875000, 6750000]
                              432
                             0.610

Sur un ordi d'aujourd'hui, et compte tenu de comparaisons faites sur un autre fil ayant amené beaucoup d'éloges pour ma machine, je suis sûr que ça irait au moins dix et peut-être cent fois plus vite. Je teste ma procédure avec un zéro de plus:

> debut := time(): gottinvphi(18000000): nops(%); time()-debut;
> 
                              847
                             0.740

@Ga? 8-) ma modestie en prend un coup !

Alors, j'ai accédé par ssh à un maple 12 sur une machine plus récente que la mienne et nettement plus rapide. Voici une comparaison:

> debut := time(): 2^5*3^5*5^3*7^3; nops(invphi(%)); time()-debut;
                              333396000

memory used=3.8MB, alloc=3.3MB, time=0.13
................etc..........................
memory used=1525.9MB, alloc=4.9MB, time=44.29

                                3664

                               44.267

> debut := time(): 2^5*3^5*5^3*7^3; nops(sort(gottinvphi(%))); time()-debut;
                              333396000

memory used=1529.8MB, alloc=4.9MB, time=44.50
................etc..........................
memory used=1587.0MB, alloc=7.4MB, time=47.03

                                3664

                                2.759

pas mécontent... j'utilise la dernière version de ma procédure (EDIT4 de mon message initial). Les durées sont à prendre au sens relatif, je crois que c'est plus rapide quand j'accède à la machine par un client sur place.

Les allocations mémoires de «invphi» semblent énormes, 1,5 Giga à comparer aux à peu près 60 Méga de «gottinvphi». C'est peut-être cela qui (au delà d'un certain seuil vite atteint) fait que sur mon ordi perso «invphi» rame lorsque qu'on lui donne un «a» trop composite. Il demande trop de mémoire et ça passe en mémoire virtuelle avec accès sur le disque dur (encore que je n'entende rien de spécial).

@Ga? Je ne sais pas précisément où est installé le maple 12 auquel j'ai accédé par ssh. Je sais que maple à l'invite de shell le lance sur un autre serveur, il est possible que cette façon d'y accéder plutôt que via un ssh direct sur la machine (dont je n'ai pas le nom) où est le maple 12 ait comme conséquence ces choses bizarre: j'ai supprimé des dizaines de lignes d'output où à chaque fois la mémoire allouée augmentait. Ou alors, le invphi des versions de maple comme 9 et 12 avait ce problème et peut-être que toi tu as une version plus récente de maple avec un invphi moins catastrophique?

Avec Maple 13:

J'ai compris que kernelopts(printbytes=false) permet de désactiver tous ces messages memory used= que je vois en mode tty (je n'ai pas l'habitude car sur mon Mac OS X, je n'ai pas d'accès à maple via un terminal). Ces données réapparaissent après avoir tapé «done» :

> done
memory used=62.4MB, alloc=6.9MB, time=2.77

lorsque j'ai utilisé «gottinvphi» et

> done;
memory used=1526.1MB, alloc=4.9MB, time=44.92

lorsque j'ai utilisé «invphi» du paquet numtheory. Sans doute je ne comprends pas précisément ce que cela signifie, ça doit être cumulatif, et ne veut pas dire que invphi a eu besoin de 1,5 G simultanément. Mais toutes ces allocations mémoires (les messages activés par printbytes=true sont à chaque «garbage collection») sont clairement liées à la lenteur de la routine sur Maple 12. J'imagine que le problème a été réglé à partie de Maple 13. Ou alors c'est mon Maple 12 qui est un l'idiot du village.

re-Bonjour
désolé j'avais encore un machin pas bien dans ma procédure. Je l'ai mise à jour: Ça va plus vite: