Bonjour,
Je propose l'intervalle [latex][v(m),v(m)][/latex], ou v est la suite définie par l'A003434, qui dépend bien de m. Je pense que l'on ne trouvera pas plus petit comme intervalle ...
Plus sérieusement, [latex]\phi(m) < m - \sqrt{m}[/latex] si m est composé
m admet au moins un diviseur p inférieur à [latex]\sqrt{n}[/latex].
Les multiples de ce diviseur apparaissent m/p fois, qui est supérieur à [latex]\sqrt{m}[/latex].
On remarque aisément que [latex]\phi(m)[/latex] est composé (ou égal à deux)
On peut donc écrire que [latex]\phi^n(m) < \phi^{n-1}(m-1) < m-n[/latex]
Donc k est inférieur à m-1. (Je bloque un peu pour utiliser efficacement l'expression avec la racine, je ne trouve pas d'expression simple, ni de majoration suffisamment efficace). 
Du côté de la minoration, On peut écrire [latex]\phi(m) = m(p-1)/p1...(pi-1)/p i> m\times1/2\times2/3\times3/4\times...\times(p-1)/p = \dfrac{m}{\sqrt m} = \sqrt{m}[/latex]
avec p le plus grand facteur premier de m.
C'est valable pour n strictement supérieur à 6 car 6 est le plus grand nombre divisible par un nombre premier supérieur à sa racine.
On déduit que [latex]\phi^n(m) > m^{\frac{1}{2n}} [/latex] tant que ce n'est pas inférieur à 6...
[TeX]m^{1/2n} \leq 6 \iff n \geq \dfrac{ln(\dfrac{ln(m)}{ln(6)})}{ln(2)}[/TeX]
Ensuite, en minimum 1 étapes, c'est plié, donc la borne inférieure de k est [latex]\dfrac{ln(\dfrac{ln(m)}{ln(6)})}{ln(2)} + 1[/latex] Je pense pouvoir faire mieux car j'ai vu de magnifiques minorations de phi sur le net, beaucoup plus fines que celle ci... Par contre, pour la majoration, ça me semble plus compliqué d'améliorer...

Améliorons notre minoration:
Le lien http://www.les-mathematiques.net/phorum … 317,395974 nous donne : [latex]\phi(m) > \dfrac{m}{ln(ln(m))}[/latex].
On en déduit aisément par récurrence que [latex]\phi^n(m) > \dfrac{m}{(ln(ln(m)))^n}[/latex]
On obtient alors [latex]k > \dfrac{ln(m)}{ln(ln(ln(m)))}[/latex] sauf erreur.
L'application de mes formules donne
13 <k< 36234
C'est un peu nul comme encadrement
mais ça doit être surtout dû à ma majoration, je vais chercher mieux dessus...
Edit: je crois que je trouve 14 pour 36235, elle a l'air assez balèze ma minoration

Bon, c'est une première réponse, je la retiens.

OEIS, heureusement, ne dit pas tout. C'est agaçant, cette référence quand on suggère une suite....

Ta minoration est très bonne, mais se détériore lorsque le nombre grandit.
Ta majoration est encore assez loin de ce que j'ai. Surtout, j'ai une valeur pour 36235 bien mieux centrée dans l'encadrement (ce nombre a été choisi au hasard)

Sinon, ta démarche est totalement différente de la mienne.

Cette suite s'analyse avec une feuille de papier et un stylo. Aucun outil n'est nécessaire. Aucune référence sur Internet n'est à rechercher. Il faut juste faire travailler ses petites cellules grises, comme dirait H.Poirot.

@ Caduk: c'est mieux déjà, mais ça dérive vite de toute façon par rapport à ma majoration. Je valide tout de même, c'est une 1ère réponse. On peut faire beaucoup mieux, et bien plus simplement (mais comme dit Vasimolo, la simplicité n'exclut pas la subtilité).   

@ tous : Les extrémités de l'intervalle, une fois qu'on a trouvé le truc, se calculent facilement à la main, sans calculette.

C'est cela, Ebichu, bravo !

A une nuance près tout de même pour la majoration, à laquelle j'ai ajouté +1 pour le majorant + 1 premier.

Ce n'est pas tout à fait l'énoncé, Vasimolo.

La question est d'avoir une formule simple qui donne un encadrement de k, le plus fin possible, quel que soit m. Si m est un nombre à 20 chiffres par exemple, ce serait sûrement très long de calculer la valeur exacte de k, et encore en s'aidant des logiciels de décomposition en facteurs premiers. Avec la formule, on peut donner un encadrement assez fin. Pour ce nombre à 20 chiffres, on peut estimer le k à 50 environ (milieu de l'encadrement).

@Sydre : c'est bon pour le majorant, qui est en effet le plus facile à découvrir. Des 2 que tu proposes, je garde le plus grand, qui convient pour tous nombres. On m'a donné ton majorant inférieur pour tout nombre, je crois que c'est bon aussi, mais je dois confirmer. Cela dit, ça ne fait pas beaucoup de différence entre les deux.

@ Sydre: pour le minorant, il y a un chouia mieux, mais c'est presque ça, bravo !
Pour le majorant, l'une ou l'autre des 2 valeurs conviennent, on en reparlera à découvert.

Si on appelle s(n) la relation qui à n donne k, peut on déduire s(abc...) si on connait s(a) s(b) s(c)..... ?