Inscription / Connexion Nouveau Sujet
Changement de couleur pour 2023
Bonjour et meilleurs vœux pour cette nouvelle année
Les nombres de 1 à 2023 sont initialement tous noirs, mais lorsqu'on choisit l'un d'entre eux , il passe de noir à multicolore (ou de multicolore à noir) en même temps que tous les nombres
qui vérifient
.
Est-il possible de faire passer en multicolore tous les nombres de 1 à 2023 pour s'assurer d'avoir une année haute en couleur plutôt qu'une année noire ?
PS : Si vous voulez remonter dans le temps et essayer avec plus petit que 2023, je ne vous en voudrais pas de nous faire rajeunir 
Bonjour et tous mes vœux pour une année heureuse, joyeuse et ... chercheuse !
Il faut un début à tout ; je nous fais donc beaucoup rajeunir :
Cliquez pour afficherD'accord Sylvieg et merci mais puisque c'est possible jusqu'à une certaine valeur, est-ce qu'on ne peut pas repartir de ce résultat pour la valeur suivante ?
D'accord Sylvieg et merci mais puisque c'est possible jusqu'à une certaine valeur, est-ce qu'on ne peut pas repartir de ce résultat pour la valeur suivante ?
Cliquez pour afficherBonjour,
On peut remarquer que ce qui compte dans l'histoire, c'est juste l'ensemble des diviseurs premiers : il arrive exactement la même chose à qu'à
.
C'est bien possible mais comment s'en convaincre ?
17.J'ai aussi mon année de naissance.
J'imagine que tu as un joli algorithme qui peut servir de démonstration quelque soit le nombre choisi et que tu as utilisé un pauvre esclave numérique pour obtenir ce résultat, me trompé-je ? En tout cas, on veut tous connaitre ton secret de fabrication.
Ça va venir, mais je laisse un peu réfléchir. Ça peut être instructif d'examiner comment on passe de 29 à 30 (voir les listes que j'ai données plus haut).
Bonsoir,
si on a une séquence qui rend multicolore les entiers de 1 à 29 alors 30 est multicolore.
En effet on a modifié un nombre impair de fois les multiples de 2, 3 et 5.
Bonsoir verdurin,
La séquence donnée par GBZM à 16h20 pour 29 ne rend pas 30 multicolore.
PS : Inutile de s'encombrer avec 1.
Il suffit de l'enlever au départ ; ce qui revient à considérer les entiers de 2 à 29.
@verdurin,
Et si tu cliquais sur un nombre pair et multiple de 3 en même temps ? Par exemple 6
En cliquant par exemple sur 6 et 5.
Soit un ensemble d'entiers >1 sans facteur carré (c.-à-d. des produits de premeirs distincts).
Pour entier >1, soit
l'entier modulo 2 qui vaut 1 si et seulement si
"change"
, c.-à-d.
. Soit aussi
, le nombre de multiple de
dans
modulo 2.
Suppososns que change tous les entiers de 2 à 29 et se composes d'entiers inférieurs ou égaux à 29.
Alors :
. De même
, d'où
. De même
Maintenant (formule du crible de Poincaré) :
Donc aucun ensemble d'entiers parmi 2,....,29 qui change tous les entiers de 2 à 29 ne peut changer 30.
Cette démonstration ne sert pas seulement à montrer que verdurin se trompe, elle donne aussi un indice pour la résolution du problème.
Bon,
Comme il n'y a pas trop de répondant, je donne le code SageMath que j'ai utilisé :
def Change_Couleur(n) :
CC=[]
for k in range(2,n+1) :
k = ZZ(k)
if k == k.radical() :
D = k.divisors()[1:]
for d in D :
if d in CC :
CC.remove(d)
else :
CC.append(d)
CC.sort()
return CCPourquoi SageMath et pas python ? Parce que je suis fainéant et que SageMath me donne accès facilement à des commandes arithmétiques qui s'appliquent aux éléments de l'anneau des entiers.
k = ZZ(k) transforme l'entier k en un élément de l'anneau des entiers, et alors
k.radical() donne lme produit des facteurs premiers distincts de k (le radical de k)
k.divisors() donne la liste des diviseurs de k, dont on peut virer 1 grâce à [1:]
Le reste est du python standard.
Ça va assez vite.
%time L = Change_Couleur(2023)Wall time: 86.9 ms
J'ai aussi écrit des fonctions de vérification :
def Change(L,k) :
c = 0
for l in L :
if GCD(k,l) > 1 :
c += 1
if c%2 == 1 :
return True
else :
return False
def Verification(L,n) :
return all(Change(L,k) for k in range(2,n+1))La vérification est plus lente que la construction :
%time Verification(L,2023)Wall time: 4.58 s
True
Ce n'est pas de la fainéantise mais de l'optimisation dans la délégation des taches
D'accord avec toi mais pourquoi ton joli code fait ce qu'on attend de lui ? Il y a quand même une raison qui nous fait choisir tous les diviseurs différent de 1 dès qu'on tombe sur un nombre qui n'est pas divisible par un carré parfait autre que 1.
Bien sûr qu'il y a une raison. Elle est assez fortement suggérée dans mes messages précédents. Je laisse encore un peu creuser qui veut.
Personne ne creusant plus, je rebouche.
On a vu précédemment que si est un entier sans facteur carré et si un ensemble
d'entiers
et
, sans facteurs carrés, fait l'affaire pour tous les entiers de 2 à
alors, avec les notations ci-dessus,
pour tout entier
sans facteur carré entre 1 et
, et
. Pour de vrai, on l'a vu seulement pour
et ses diviseurs stricts, mais le même raisonnement à base de formule du crible de Poincaré s'applique généralement.
Pour faire l'affaire de 2 jusqu'à , on fait la différence symétrique de
avec l'ensemble des diviseurs
de
; notons
cet ensemble de diviseurs, on prend donc
.
Pour tout entier sans facteur carré, on a
. Or
si
et
. Donc
fait bien l'affaire pour tous les entiers de 2 à
.
Annuler
connectez vous