Suite périodique
dans Arithmétique
Bonjour @ tous.
Soit k de N, p un nombre impair, p < 2 ^ k -1, et la suite :
U0 = p
U(n+1) = Un + ( 2 ^ k -1) si Un impair et Un / 2 si Un pair.
Cette suite est évidemment périodique. Montrer que le nombre de nombres impairs dans la période, pour p donné, peut prendre au plus 2 valeurs selon k.
Bonne recherche
Soit k de N, p un nombre impair, p < 2 ^ k -1, et la suite :
U0 = p
U(n+1) = Un + ( 2 ^ k -1) si Un impair et Un / 2 si Un pair.
Cette suite est évidemment périodique. Montrer que le nombre de nombres impairs dans la période, pour p donné, peut prendre au plus 2 valeurs selon k.
Bonne recherche
Réponses
-
Salut Nodgim,
n'y a -t-il pas une coquille dans ta définition de U?
Tu emploies la lettre "n" à la fois pour désigner un naturel fixé et un naturel variant.
Paul -
OK, Depasse.
Il y a un autre bug, plus embêtant, dans l'énoncé.....
Je regarde de près avant la correction. -
Bug corrigé.
Bonne recherche. -
Bonjour,
Ce que je pense avoir établi n'est peut-être pas clairement en adéquation avec l'énoncé proposé, que je n'ai pas bien compris
$\forall k \in\N^*$, je note $E_k$ l'ensemble des entiers impairs inférieurs à $2^k-1$.$\:\:\:\forall n \in \N,\:\: \mathcal I(n)$ désigne le plus grand entier impair divisant $n$
$\forall x \in E_k, \:\: \Phi_k(x):= \mathcal I(x + 2^k-1)$
Ainsi , la suite $v^x$ définie par $v^x_0 =x$ et $ \forall n \in \N,\:\: v_{n+1}^x = \Phi_k(v_n^x)$, est la suite des nombres impairs obtenue, à partir d'un $x\in E_k$, par la procédure décrite par l'énoncé. Alors
$\bullet \:\:\:\Phi_k$ réalise une permutation de $E_k$ , ce qui entraine la périodicité de $v^x$.
$ \bullet\:\:\:\forall i \in [\![1; k-1]\!], \:\:\: \exists x \in E_k$ tel que $v^x$ soit de période $i$.
$ \bullet \:\:\: \forall x \in E_k,\:\:$ la période de $v^x$ divise le nombre de $1$ que contient l'écriture en base $2$ de $x$
$\bullet \:\: $ si $p$ est un nombre premier dans $E_k$, alors la période de $v^p$ est soit égale à $1$ , soit égale au nombre de $1$ de l'écriture binaire de $p$
$\bullet \:\:\:$ Le nombre de points fixes de $\Phi_k$, (i.e. de $x \in E_k$ tels que $v^x$ est de période $1$) est égal au nombre de diviseurs de $k$.
Par exemple, avec $k =6$, les cycles disjoints qui déterminent $\Phi_k$ et donc les périodes des suites $v^x$ sont:
$(1);\: (63);\: (21);\: (9);\: (3, 33);\: (5, 17);\: (7,35, 49);\: (11,37, 25);$$(13,19, 41);\: (15, 39, 51, 57) ;\: (23, 43, 53, 29 );\: (31, 47, 55, 59 , 61), $
et ce dernier, que j'avais oublié, détecté dans un message ultérieur par l'oeil de lynx de Depasse que je remercie: $(27,45)$. -
C'est bien cela LOU16, bravo à toi, tu as vu l'essentiel !
Juste une petite précision pour se rapprocher de l'énoncé :
39 par exemple s'écrit 100111 en binaire. La période de la suite dont il fera partie comprendra 4 nombres impairs puisqu'il a 4 " 1 ", et cela quel que soit k. Comme il ne présente aucune amorce de répétition, aucune possibilité d'avoir un cycle raccourci.
En revanche, 11011 peut avoir un cycle raccourci avec 2^6 -1 :
110_110 (poids faible à gauche)
101101 en ajoutant 2^6-1 une première fois
11011 en ajoutant 2^6-1 une seconde fois.
11011 (27, nombre fétiche pour Syracuse) a donc 2 périodes possibles :2 pour k = 6 et 4 pour tout autre k.
Tout nombre impair présente donc, dans le cas général, une seule période, et, éventuellement, une période raccourcie pour un seul cas.
Je ne crois pas qu'il y ait un quelconque rapport avec la primalité de p, ce que je crois avoir lu dans ta réponse. Ou alors j'ai mal compris, ou quelque chose m'a échappé. -
Non, tu as raison : pour tout entier impair $x$, il n'y a que deux longueurs de période possibles pour $v^x$. ( et je n'ai pas mentionné cela): "pour toutes les valeurs de $k$ sauf au plus une" , cette longueur est égale au $\text{nombre de }1$ contenus dans l'écriture binaire de $x$.
Ce qui est spécifique aux nombres premiers $p$, c'est que la longueur de la période de $v^p$ est égale
$\bullet\:\:$ à $1\:$ lorsque $p$ et $k$ sont tels que $ p = \displaystyle \sum _{i=0}^{s-1} 2^{ti}\:\: \text{avec}\:\:\: t,s \in \N, \: ts = k, \:\: k \:\:\text{impair}.$.
$\bullet\:\:$ au $\text{nombre de }1$ de l'écriture binaire de $p$, sinon.
Si $x$ n'est pas premier, alors la longueur de la période de $v^x$ peut être différente de $1$. -
OK, ça marche.
-
Bonsoir,
il me semble que LOU a oublié le cycle fétiche de Nodgim: $(27, 45)$
Amicalement
Paul -
Le 27 est en effet un nombre pas commun pour Syracuse. Avec ses malheureux 5 chiffres binaires, il réussit à tenir 41 itérations ( multiplications par 3) avant de revenir sur 1. Il a un ratio de réussite de 41/5. Pour trouver un meilleur score, il faut aller chercher le nombre 230631 ( 18 chiffres binaires) qui tient 163 itérations. J'ignore si ce ratio a une limite.
-
Bonjour,
On peut essayer $670617279$.
Cordialement,
Rescassol -
'Les mathématiques ne sont pas encore prêtes pour ce genre de problème', Paul Erdos.
Al-Kashi -
@ Rescassol : le nombre d'itérations (986) ne compte que les nombres impairs ?
-
Bonjour,
Non, toutes les itérations.
Cordialement,
Rescassol -
D'accord, je m'en doutais un peu.
Merci à toi. -
Bonjour,
Si on ne compte que les impairs, il y en a $370$.
Cordialement,
Rescassol -
OK, merci Rescassol.
Ratio : 370/29 = 12,7....
ça progresse mais très lentement.... -
Bonsoir,
Le degré d'un mot $M$ est le plus grand des entiers $e$ tels qu'il existe un mot $m$ vérifiant $m^e=M$ (au sens de la concaténation).
Si $M$ est une écriture d'un entier $x$ en base deux, $0M$ l'est aussi.
Tout entier non nul a au plus une écriture en base deux dont le degré n'est pas $1$.
Pour tout $k \in \mathbb N$, pour tout $x \in E_k$,
$deg(k,x)$ abrègeant " le degré de l'écriture de $x$ en base deux de longueur $k$ " et $w(x)$ "le nombre de $1$ dans cette écriture",
la période de $v^x$ est $\dfrac{w(x)}{deg(k,x)}$.
Le fait que ni Lou ni Nodgim n'ait assuré que la période de $v^x$ est, sauf cas exceptionnel (i.e. $deg (k,x) >1$) le poids de $x$ en base deux me fait douter de mes affirmations sans preuves!
A suivre
Amicalement
Paul -
Bonsoir Dépasse,
Je profite de ta présence sur ce fil pour te saluer.
Al-Kashi -
Bien le bonjour à toi aussi.
Cordialement
Paul
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres