Bon benh maintenant que j'ai tout lu ce que tout le monde propose j'attends la réponse élémentaire

scrablor a écrit:

Je ne comprends pas... Pourquoi ne pourrions-nous pas avoir au bout d'un certain nombre d'étapes quelque chose du genre ...17+7=24, 12, 6, 3, 3+7=10, 5, 5+7=12, 6, 3... ?
Bon, je sais, n=7 n'est pas un bon exemple, mais c'est pour éclaircir ma question.

Nodgim a parfaitement raison, je suis allé trop vite sur le point que l'antérieur est unique.

J'appelle N l'entier de départ et u(n) la suite constituée par les impairs de l'algorithme.

On a:
1<= u(n) <= N
1<= u(n+1) <= N
et N+u(n)= 2^p*u(n+1)

Supposons qu'il existe u'(n) un antérieur supérieur à u(n)
Alors N+u'(n) = 2^(p+q)*u(n+1).

On a u'(n)-u(n) = (2^q-1)*2^p*u(n+1)=(2^q-1)(N+u(n))
Donc u'(n)= (u(n)+N)*2^q

Comme u(n)>=1, il vient u'(n)>=2^q*(1+N)
Alors que tous les membres de la suite sont inférieurs ou égaux à N.

J'espère que c'est juste...

J'ai essayé de le programmer en python mais ça marche pas ...

Bien qu'il y ait eu des réponses correctes, je laisse tout de même encore dérouler pour les questions résiduelles, je n'ai pas vraiment la possibilité de développer en ce moment.
@ bientôt

Je n'y ai pas encore réfléchit par manque de temps mais il serait bien de trouver une formule qui donne le n-ième terme de la suite afin de trouver les points fixes de la suite. Je serai curieux de voir si la suite (2^n) est un point fixe ou non, et donc a fortiori 1 par divisions successives par deux.

PS : Désolé pour le doublon mais je voulais que ce message soit visible à part de mon programme.

Le programme en langage TI82 que j'avais fait :

:0->C
:Prompt A
:C+1->C
:A+1->B
:Lbl 1
:C+1->C
:Disp B
:If B/2=ipart(B/2)
:Then
:B/2->B
:Else
:B+A->B
:End
:Pause
:If B=1
:Then
:Goto 2
:Else
:Goto 1
:Lbl2
:Disp 1
:C+1->C
:End
:Disp C

Il faut appeler le script avec le nombre impair de départ en paramètre.
Chaque ligne de sortie correspond à l'obtention d'un nombre impair (le détail des divisions par 2 n'apparaît pas).

import sys
N=int(sys.argv[1])

n=N+1
if n%2 : exit()
k=0; t=0
print("%3d %3d %3d"%(k,N,t))
while True:
    while not(n%2): n//=2; t+=1
    k+=1; t+=1
    print("%3d %3d %3d"%(k,n,t))
    if n==1: break
    n+=N

Par exemple, pour N=11

  0  11   0
  1   3   3
  2   7   5
  3   9   7
  4   5  10
  5   1  15

Sur chaque ligne :
numéro d'ordre du nombre impair + le nombre impair + nombre total d'opérations (le nombre de départ est numéroté 0)

Pour ma part je suis parti d’un "bête" tableur qui donne des résultats identiques qui ne sont néanmoins pas une vraie preuve. Je reste d’ailleurs un peu sur ma faim, dans l’attente de la "démonstration assez courte" de nodgim qui ne fait pas "appel à des connaissances arithmétiques", à moins que ce soit celle, correcte mais longue, de golgot59 ?

On attend toujours la réponse élémentaire...

J'ai testé jusqu'à n=10^9 et ça marche.

Donc c'est juste

Prenons l'énoncé suivant : Soit p premier, m entier tel que 0<m<p et n entier tel que n=m modulo p
On considère l'algo suivant :
- on part de N=n+1
- si N est divisible par p, N' = N/P
- sinon N' = N+n
- et on boucle
Trouve t'on toujours 1 ?
N.B. : on considère qu'on ne s'arrête pas à 1. On continuera de boucler, en retombant sur le même premier terme. Ca ne change pas le problème pour autant.

Soit a tel que p^a < n < p^(a+1).
On va exclure directement le cas n = p^(a+1)-1, qui mène à 1 directement.
On va aussi exclure le cas n=1, encore plus trivial.
Enfin, on ne considère que certains termes de la suite : ceux où on passe de l'addition à la division et vice-versa.
Autrement dit, l'algorithme se résume à la suite U suivante:
- U1 = n+1
- Si U(k)=p^i * j avec j et p premiers entre eux, alors U(k+1) = j
- Sinon U(K+1) = U(K)+az avec U(k+1) multiple de p et z le plus petit possible (existe toujours d'après la propriété 1).


Propriété 1 : quel que soit m' entier entre 0 et p-1, il existe un k tel que km=m' modulo p.
Démonstration :
- pm = 0 modulo p
- soient a, b deux entiers tels que 0 < a < b < p.
Si am = bm modulo p, alors (b-a)m est un multiple de p. Comme p et m sont premiers entre eux, alors (b-a) est un multiple de p. or, b-a<p donc b=a, ce qui est absurde.
Conclusion : pour tout k tel que 0<k<p, on a p-1 valeurs différentes pour k et ce pour p-1 valeurs différentes pour km modulo p. Donc toutes les p-1 valeurs sont rencontrées.

Propriété 2 : les termes de U sont majorés par np+1.
Démonstration : par récurrence
- U(1) = n+1 < np+1
- Si pour tout k <= K , U(k) < np+1, alors
* U(K) multiple de p implique U(K+1)<U(k)<np+1
* sinon, U(K) n'est pas multiple de p, donc U(k-1) l'était. U(k-1)< np+1, donc U(k) <=np/p <= n
Dans ce cas, U(k+1) <= U(k) + (p-1)n <= n +np -n = np < np+1

Par ailleurs :
- en sortie de division, on part d'un terme <= np, donc on a un terme <= n
- en sortie d'addition, on ajoute n a minima une fois, donc on a un terme > n


Propriété 3: chaque terme n'a qu'un seul antécédent.
Démonstration :
- Si U(k) est divisible par p, alors son antécédent est de la forme U(k)-nz avec z entier.
S'il existe 2 antécédents, alors il existe Z et Z' distincts tels que 0<Z<Z' et nZ = nZ' modulo p.
Donc Z=Z' modulo p, donc Z' = mp + Z avec m>=1
U(k) < np+1
nmp >= np
U(k)-nZ' = U(k) -nmp -nZ < np+1 - np-nZ = 1-nZ <0
Donc U(k)-nZ' négatif, ce qui est absurde.
Dans le cas où U(k) est divisible par p, il n'a donc qu'un seul antécédent de la forme U(k)-nz avec z entier.
- Si U(k) n'est pas divisible par p, alors son antécédent est de la forme U(k)*p^z. C'est un terme issue d'addition, donc supérieur à n.
On a : p^a < n < U(k)*p^z < np+1 < p^(a+1)
S'il existe deux valeurs Z et Z' pour z, avec 0<Z<Z', alors posons Z'=Z+x avec x >= 1
On a U(k)*p^Z' = U(k)*p^Z*p^x donc p^(a+x) < U(k)*p^Z' < p^(a+x+1)
Par conséquent, p^(a+1) < U(k)*p^Z', ce qui est absurde.
Dans le cas où U(k) n'est pas divisible par p, il n'a donc qu'un seul antécédent de la forme U(k)*p^z avec z entier.


Propriété 4: les termes de U se répètent tous.
Démonstration :
- Tous nos termes sont entiers et majorés par np+1. Par conséquent, il existe au moins un entier qui sera par deux fois terme de U, donc la suite sera périodique à partir d'un certain rang.
- Soit K>1 le rang du premier terme à partir de laquelle la suite devient périodique (de période T), on a
* U(K) = U(K+T)
* U(K-1) != U(K+T-1)
Or, U(K-1) et U(K+T-1) sont deux antécédents de U(K) puisque U(K+T) = U(K). C'est impossible d'après la propriété 3.
Donc le premier terme à partir de laquelle la suite devient périodique est U(1), c'est à dire n+1



La fin se déroule d'elle même:
- on démarre à n+1
- on y retournera d'après la propriété 4.
- son antécédent ne peut pas être (n+1) * p^z, puisque np+1 < (n+1)p <= (n+1)p^z, c'est donc (n+1)-n*z, valide si et seulement si n=1, autrement dit 1.

CQFD

Je n'avais pas donné ma réponse, qui est en fait très simple, car elle est induite d'un principe facile à comprendre:
Si dans une suite de nombres fournie par un algorithme, l'intervalle des valeurs possibles est fini, et si on peut montrer que l'antécédent est unique, alors nécessairement, on reviendra à la 1ère valeur de la suite.
En effet, s'il n'y a qu'un seul antécédent possible, on ne peut pas entrer dans une boucle par une valeur extérieure à celle ci, sinon ce serait en contradiction avec l'unicité de l'antécédent.
Dans le cas de l'énoncé proposé, la valeur initiale est 1, l'unicité de l'antécédent et la limitation de l'intervalle des valeurs possibles se vérifient facilement: on retrouvera donc la valeur 1 après un certain nombre d'itérations.