Bonjour,
questions pour commencer:

Spoiler : [Afficher le message]
- montrer que tout nombre > 1 converge

suite décroissante car np > n + p pour n et p supérieurs à 2
np = (n-2)(p-2) + 2(p-2) + 2(n-2) + 4 > p - 2  + n - 2 + 4 =  p + n
(égalité si p - 2 = n - 2 = 0 soit p = n = 2)
par récurrence immédiate, un produit de facteurs est supérieur à la somme des facteurs

La suite n'est pas strictement décroissante si il n'y a pas deux facteurs  > 2, donc si on a un nombre premier, ou si les deux seuls facteurs sont 2 et 2, donc 4 est aussi un point fixe (et le seul non premier)

- montrer que tout nombre premier > 3 peut être le résultat d'un r(N) avec N composé

4 = r(4) ou 4 est composé
C'est la seule manière d'obtenir 4, car la seule manière de décomposer 4 en somme de facteurs positifs supérieurs à 2 est 2x2

pour tout nombre premier p supérieur à 3 (donc impair)
si p  = 3n+1, p = r( 3^(n-1)*4 )
si p = 3n+2, p = r( 3^(n-1)*5 )

Pour l'algo, on pourra le coder en programmation dynamique avec la récurrence r(N) = r(s(n)) tout simplement, mais j'ai un peu la flemme, surtout que je suis à peu près certain que c'est c que tu as fait. Je ne vois pas comment on pourrait améliorer cette complexité, sauf à trouver un théorème génial sur les nombres premiers, et dieu sait que ce n'est surement pas moi qui le sortira...

La dernière observation sur les nombres premiers jumeaux est intéressante et mérite sans doute un peu d'attention...
Edit:
Soit n et n+2 premier
Après réflexion, ce phénomène est sans doute lié au fait que pour tout nombre tel que r(n) = n, alors r(2n) = n+2, mais il faudrait faire une analyse plus rigoureuse...

Je pense effectivement que l'on doit pouvoir améliorer le simple algorithme en programmation dynamique...

Je pense à un algorithme qui procéderait de cette manière:

On construit une liste de structure contenant les éléments suivants:
- nombre de prédécesseurs : int n.nbrPred
- successeur n.succ
chaque structure étant associée à un entier entre 2 et M = 100000000

Tant que l'on est inférieur à M:
    Sélectionner le premier élément p p.succ = vide (il est premier)
    p.succ = p
    p.nbrPred = p.nbrPred + 1
    Pour i allant de 2 à M/p:
        Si i.succ != vide:
            désigner (i*p).succ = i+p.succ
            fils = i + p.succ
            Tant que (fils.succ != vide) ou (fils.succ != fils):
                fils = fils.succ
            fils.nbrPred = fils.nbrPred + (i*p).nbrPred + 1

Pour mieux comprendre, voici ce qu'il se passe durant l'exécution:
Le premier élément ne possédant pas de successeur est 2, son successeur devient 2, son nombre de prédécesseur devient 1
p = 2
On parcourt pour i allant de 2 à M/2:
     i = 2
     succ(2) est non vide, donc 2+2 = 4 est désigné successeur de 2*2 = 4, son nombre de prédecesseurs devient 1.
    comme succ(4) = 4, on n'entre pas dans le deuxième Tant que.
    i = 3
    le successeur de 3 est vide
    i = 4
    le successeur de 4 est non vide
    6 est désigné successeur de 8, le nombre de prédécesseur de 6 devient 1
    ...
    Toutes les puissances de 2 inférieures M ont donc un successeur

p = 3
On parcourt pour i allant de 2 à M/3:
    i = 2
    succ(2) est non vide donc 6 recoit 5 comme successeur, le nombre de prédécesseur de 5 devient 1 + 1 = 2 (6 avait déjà un prédécesseur)
   succ(5) = vide, on n'entre pas dans le Tant que
   i = 3
   9 recoit 6 en successeur
   On descend parmi les fils, et on s'arrête à 5 (car succ(5) = vide)
   donc le nombre de prédécesseur de 5 devient 2 + 1
   ...
   Tous les nombres ayant comme unique facteurs 2 et 3 et inférieurs à M ont donc un successeur

p=4 a un successeur

p = 5
5 a maintenant 4 prédécesseurs
On parcourt pour i allant de 2 à M/5:
    i = 2
    10 recoit 7 en successeur, 7 a alors 2 prédécesseurs
    i = 3
    15 recoit 8 en successeur
    après descente des fils, 5 recoit un nouveau prédécesseurs, il en a donc maintenant 5.

Et ainsi de suite...

Je suis assez occupé en ce moment donc je n'ai pas le temps de le coder, je verrais plus tard peut être. En tout cas, la comparaison en temps risque de ne pas être juste, mon ordi portable n'étant vraiment pas très puissant (surtout ces derniers temps je trouve...)