Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 19-04-2017 14:03:12

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Somme de facteuurs premiers - enigme en partie à coder

Je me suis intéressé récemment, à titre de curiosité, aux fonctions suivantes:
- s(n) qui à un entier n supérieur à 1 fait correspondre la somme de ses facteurs premiers
- r(n) définie de la manière suivante
  - si s(n) = n, alors r(n) = n
  - sinon r(n) = r(s(n))

Plus simplement, je prends un entier, je calcule la somme de ses facteurs premiers, j'obtiens un autre nombre, et je recommence jusqu'à obtenir un nombre premier.
Ainsi:
- 8 = 2x2x2 ==> j'obtiens 2+2+2 = 6, puis 6 = 2x3 ==> j'obtiens 5
- 57 = 3x19 ==> 22, puis 11x2 ==> j'obtiens 13
etc...

Quelques questions d'analyse pure pour commencer
- montrer que tout nombre > 1 converge
- montrer qu'il n'existe qu'un seul point fixe non premier
- montrer que tout nombre premier > 3 peut être le résultat d'un r(N) avec N composé


Maintenant, la partie à coder.
Le but est d'écrire un algo performant pour calculer les r(n) pour n inférieur à une limite donnée.
Si vous voulez tester le votre, la case réponse valide la somme de tous les r(n) avec 1 < n < 100000000 - à titre d'info le résultat sort en un peu moins de 7 secondes en C et un peu plus de 7 secondes en C#.

Et pour aller encore plus loin, à partir de là, j'aimerais trouver une certaine logique dans la répartition des nombres premiers atteints. 5 et 7 reviennent bien entendu le plus grand nombre de fois, mais je me demande s'il y a une logique derrière. Peut-être que l'un d'entre vous aura un éclair de génie, pour ma part je n'ai pas encore été gâté à ce niveau là smile
Ci dessous les premiers décomptes par résultat (pour la même limite à 100 millions)
5 25824840 fois
7 14949082 fois
11 5772374 fois
13 6445693 fois
17 2965764 fois
19 3592741 fois
23 2193365 fois
29 1196433 fois
31 1505836 fois
37 910047 fois
41 768010 fois
43 1085644 fois
Les quelques observations que j'ai déjà pu faire
- C'est globalement décroissant, mais bon on pouvait s'en douter
- 5 couvre en général une très large partie des résultats
- Quand on a 2 nombres premiers jumeaux, le second est plus atteint que le 1er, mais par pour 5 et 7

Je ne masque pas le topic, je pense que c'est la discussion qui sera plus intéressante que les questions théoriques ou le code. Et mon but est aussi de progresser sur le sujet, donc...


 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 19-04-2017 14:49:16

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Somme de facteurs premies - enigme en partie à coder

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...

 #3 - 19-04-2017 15:45:45

scarta
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 1934

Somme de facteurs premiers - enigm een partie à coder

C'est marrant que tu passes par les modulo 3 pour le dernier point. Par 2 ça marche aussi (et c'est plus simple puisqu'ils sont tous impairs ^^)
Sinon, oui, la 1ere version de mon code était de la programmation dynamique comme celle que tu indiques; mais c'était assez lent. Au final il faut creuser un peu plus pour optimiser le calcul de s(n) et obtenir quelque chose de vraiment rapide.
Et en effet, concernant les nombres premiers jumeaux, le second pourrait être mieux servi que le premier grâce à r(2p) = p+2, ainsi le second jumeau aurait un antecedent beaucoup plus rapidement que le premier.
De manière générale, ça semble d'ailleurs être le cas. Plus un nombre et ses premiers antecedents sont petits, plus il reviendra.
Et ça explique même le cas du 5, puisqu'il est doublement jumeau (et que son unique antecedent est avant 7)

 #4 - 20-04-2017 16:19:39

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

oSmme de facteurs premiers - enigme en partie à coder

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

Code:

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...)

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez (numériquement) à la petite énigme suivante : 

Un berger a 30 moutons, ils meurent tous sauf 15, combien en reste-t-il ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete