Bonjour

Si je dis 77 je suis loin du compte

Imod

Bonjour,
Déjà pas si simple d'arriver à40 ...alors 77 tu devrais gagner

avec 77 Imod dépasse mon élève (et moi aussi !!) et tu as donc le top

en regardant sa liste je pensais qu'on pouvais faire un peu mieux aussi (mais avec la reprise pas trop le temps de m'y plonger à fond)

le problème c'est les nombres premiers p ou multiples de deux premiers q = ab avec a et b premiers : évidemment 1 divise tout le monde mais ensuite il faut jongler avec ces nombres q pour choisir a ou b à un moment ou pour ceux inférieurs à 50 prendre un multiple de q permettant de sauvegarder les diviseurs a et b pour la suite ...

En fait ce problème a traîné sur la toile il y a quelques années à un moment où j'avais pas mal de temps libre . La valeur que j'ai donnée est la meilleure possible ( prouvée sans ordinateur ) . Je ne donne pas "la" solution pour laisser chacun s'amuser . Je proposais aussi régulièrement un exercice du même style mais plus simple à mes élèves de 5ème , c'est très formateur et permet de comprendre entre autre l'intérêt des nombres premiers .

Imod

oui on peut attendre un peu encore ...

ensuite j'accepterai volontiers ta solution avec preuve (ou élément de preuve) ... éventuellement la poser ici aussi ...

je pense qu'un PDF sera accepté si c'est vraiment long

bonne soirée

On peut visualiser la chose comme un graphe. On relie toutes les paires de nombres non premiers entre eux. Je l'ai fait de 1 à 10 et on constate plusieurs choses :

Les nombres premiers plus grands que sqrt(n) ne pourront être biffé qu'après 1, donc sont des cul de sac (début ou fin)

1 peut être biffé après n'importe qui et avant n'importe qui, donc c'est un passage stratégique

chaque passage par un nombre enlèvera 2 liaisons à ce nombre. On ne pourra pas forcément tout faire, selon les noeuds qui ont un nombre impair de connexions.
En particulier, certains nombres ont peu de connexions (7 en a une, 9 et 5 en ont deux). Cela restreint donc les possibilités, et on ne pourra pas passer par tout le monde à cause du 1 qui ne peut être utilisé qu'une seule fois. Essayons de mettre de côté le 7, pour réaliser la séquence 3-9-1-5-10

Après le 10 ne peut venir que le 2
Avant le 3 ne peut venir que le 6
on a donc 6-3-9-1-5-10-2
Il reste alors à placer 8 et 4, sans problème après le 2.
6-3-9-1-5-10-2-4-8 est la plus longue séquence pour n=10

Voyons pour 100

Bonjour,

J'en suis à 53.

38
76
19
95
1
69
23
92
46
2
42
14
70
35
7
56
28
84
12
96
16
64
32
4
40
10
50
25
75
15
30
90
5
55
11
88
44
22
66
3
6
60
20
80
8
48
24
72
18
36
9
99
33

Peut-on biffer un nombre déjà biffé, si c'est une connexion différente ? Par exemple : 5 10 30 5 25
Je présume que non

EDIT : Bien sûr que non, je viens de voir la définition de "biffer"

J'ai réalisé un script qui génère le graphe et cherche une séquence aléatoire. J'ai aussi créé un script amélioré qui recherche une séquence aléatoire en s'assurant qu'on ne biffe 1 que si on ne peut biffer que lui. ça permet d'éviter de le prendre pour rien

Dans les deux cas, on ne trouve qu'une cinquantaine de termes

Juste pour l'anecdote j'ai trouvé une suite de longueur 60 sur plusieurs dizaines de milliers de tentatives

 Cliquez pour afficher

[85, 17, 34, 68, 4, 92, 46, 23, 69, 3, 78, 39, 13, 52, 26, 2, 38, 19, 95, 5, 25, 75, 15, 90, 45, 9, 99, 11, 88, 44, 22, 66, 33, 1, 50, 10, 30, 6, 36, 12, 84, 42, 7, 35, 70, 14, 28, 56, 8, 64, 32, 96, 16, 48, 24, 72, 18, 54, 27, 81]

Bonjour ,
On observe la complémentarité des chaines decandide2C, et de ZormucheZ.
*l'excellent début de Z  de 1 à 19 et l'absence de 20
*bien sûr l'absence de nombreux premiers>23. (C et  Z)
*les trous  entre 47 et  67  (12/20)   (C et Z).
Il y a certainement des ponts possibles ....

J'ai un pdf de cinq pages ( dont je ne suis pas l'auteur ) qui donne un exemple de solution et explique pourquoi on ne peut pas faire mieux . Je vais tout de même attendre un peu avant de le poster car le problème est amusant à chercher et qu'il toujours trop tentant de jeter un coup d'œil à la solution  quand elle est à portée de main .

Les stratégies proposées jusqu'ici sont plutôt bonnes

Imod

S'il y a des curieux

Trois-cent-trente-sept mille cent-vingt-cinq

S'il s'agit du nombre d'essais , on a une preuve que la force brute ne résout pas tout dans un temps fini qui est le nôtre   
Imod

Pas du tout c'est un index OEIS 😁😁

OK , le monstre qui stocke toutes les séquences d'entiers
Imod

Bonjour carpediem
Par simple curiosité que vaut ??+2

mon élève avait trouvé 69 puis immédiatement il me dit en fait qu'on pouvait remplacer les deux premiers par quatre autres restants donc 71

ce qui est très bien quand on voit le top proposé par Imod

Pour les courageux le pdf dont j'ai parlé .


PDF - 113 Ko

merci beaucoup

je regarderai cela ce we ... à moins que j'aille aux champignons ...