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
[+]

 #26 - 20-06-2015 13:17:13

emmaenne
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3058
Lieu: Au sud du Nord

Algorithme vugaris simplex

Vasimolo a écrit:

C'est qui le maladroit qui nous fait un écran d'un km de large sad

Vasimolo

C'est golgot message 6 (chut! )


Dans le cadre de la quinzaine du beau langage, ne disez pas disez, disez dites. (Julos Beaucarne)

#0 Pub

 #27 - 20-06-2015 17:36:03

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Algorithme vulgaris smiplex

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


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #28 - 20-06-2015 18:48:42

fix33
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1198
Lieu: Devant un clavier depuis 1748

Algorithem vulgaris simplex

Je crois qu'avec des vecteurs colinéaires d'espace non euclidien on devrait pouvoir donner une réponse assez élémentaire lol lol lol


Je ne vien sur se site que pour faire croir que je suis treise intélligens.

 #29 - 20-06-2015 18:50:55

papiauche
Sa Sainteté
Enigmes résolues : 49
Messages : 2125

Algorithme vulgariis simplex

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


"Je ne lis jamais un livre dont je dois faire la critique. On se laisse tellement influencer." O. Wilde

 #30 - 20-06-2015 20:10:18

scrablor
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 933

Algorithme vulgaris siplex

u(n) et u(n+1) sont forcément premiers entre eux car u(n) est premier avec N et (2^k)u(n+1)-u(n)=N.
Je voulais savoir pourquoi u(n) et u(n+2) sont différents...
Spoiler : [Afficher le message] Quel chieur, ce scrablor !


Celui qui fuit les casse-tête ne vaut pas un clou.

 #31 - 20-06-2015 23:06:05

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Algorithme vulgaris simplexx

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


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #32 - 21-06-2015 08:45:54

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

Algorithme vulgaris simpex

Bonjour,

shadock #31 a écrit:

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

Peux-tu montrer ce que tu as fait ?

 #33 - 21-06-2015 13:27:53

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

alhorithme vulgaris simplex

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

 #34 - 21-06-2015 14:16:55

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Algorithme vularis simplex

En fait c'est bon ça marche !

Le code en Python 3.3 pour trouver les termes chaque suite

Code:

def t(n): 
    L=[]
    b=n-1
    if n==0 or n==1:
        return 1
    else:
        while n != 1:              # Tant que n est différent de 1
            if n % 2==0:           # Si n est divisible par 2
                n=n//2             # On le divise par deux
                L.append(n)        # On ajoute le résultat à la liste
            else:                  # Sinon
                n = n+b            # On ajoute le nombre du départ au résultat obtenu par division
                L.append(n)        # Et on l'ajoute à la liste
    return [b,b+1]+L, len(L)+2     # Afficher la liste, Afficher la longueur de la liste

Pour reprendre l'exemple de Golgot avec 131 on obtient :

Code:

([131, 132, 66, 33, 164, 82, 41, 172, 86, 43, 174, 87, 218, 109, 240, 120, 60, 30, 15, 146, 73, 204, 102, 51, 182, 91, 222, 111, 242, 121, 252, 126, 63, 194, 97, 228, 114, 57, 188, 94, 47, 178, 89, 220, 110, 55, 186, 93, 224, 112, 56, 28, 14, 7, 138, 69, 200, 100, 50, 25, 156, 78, 39, 170, 85, 216, 108, 54, 27, 158, 79, 210, 105, 236, 118, 59, 190, 95, 226, 113, 244, 122, 61, 192, 96, 48, 24, 12, 6, 3, 134, 67, 198, 99, 230, 115, 246, 123, 254, 127, 258, 129, 260, 130, 65, 196, 98, 49, 180, 90, 45, 176, 88, 44, 22, 11, 142, 71, 202, 101, 232, 116, 58, 29, 160, 80, 40, 20, 10, 5, 136, 68, 34, 17, 148, 74, 37, 168, 84, 42, 21, 152, 76, 38, 19, 150, 75, 206, 103, 234, 117, 248, 124, 62, 31, 162, 81, 212, 106, 53, 184, 92, 46, 23, 154, 77, 208, 104, 52, 26, 13, 144, 72, 36, 18, 9, 140, 70, 35, 166, 83, 214, 107, 238, 119, 250, 125, 256, 128, 64, 32, 16, 8, 4, 2, 1], 196)

Si on veut directement le nombre de termes

Pour allez plus vite on enregistre pas les termes de la suite, on les comptes seulement, ils ne restent pas en mémoire ! smile

Code:

def h(n): 
    aaa=[]
    b=n-1
    c=0
    if n==0 or n==1:
        return 1
    else:
        while n != 1: 
            if n % 2==0: 
                n=n//2
                #aaa.append(n)
                c+=1
            else: 
                n = n+b
                #aaa.append(n)
                c+=1
    return c+2

Pour n=10.000.000 on trouve 177867 et pour dix fois plus on trouve 22955 comme quoi ...
Shadock smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #35 - 21-06-2015 14:20:51

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Allgorithme vulgaris simplex

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

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


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #36 - 21-06-2015 19:11:27

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

Algorithme vulgaaris simplex

@shadock : J'ai fait un peu différemment, mais suis d'accord avec tes résultats.

 #37 - 21-06-2015 19:49:04

golgot59
Elite de Prise2Tete
Enigmes résolues : 48
Messages : 1374
Lieu: Coutiches

Algorithmme vulgaris simplex

Le programme en langage TI82 que j'avais fait :

Code:

: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

 #38 - 21-06-2015 22:33:30

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Algorithme vulgaris simpex

Tu as fais comment enigmatus ?


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #39 - 22-06-2015 07:19:21

enigmatus
Professionnel de Prise2Tete
Enigmes résolues : 0
Messages : 400

Allgorithme vulgaris simplex

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

Code:

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

Code:

  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)

 #40 - 22-06-2015 17:40:33

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

algorithme vulgaeis simplex

Tu as quelques années de programmation derrière toi a priori, moi je suis un débutant ^^


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #41 - 22-06-2015 17:56:24

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 2714
Lieu: Luxembourg

Algorithme vuglaris simplex

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 ?

 #42 - 22-06-2015 21:26:58

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Algorithme vulgaris simmplex

Il n'a peut-être pas la démonstration, c'est pour ses devoirs roll


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #43 - 26-06-2015 20:08:47

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

algorithme vulgaris simolex

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


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #44 - 26-06-2015 22:28:00

scrablor
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 933

Algorithm evulgaris simplex

Prenez un nombre n non divisible par 3 et ajouter lui 1 au départ, divisez le par 3 autant de fois que possible, puis ajouter n au résultat, qu'on divisera encore par 3 autant de fois que possible, et ensuite ajoutez n et ainsi de suite...
Ma calculette me dit que l'on obtient 1 au bout d'un certain temps, du moins pour n assez petit.
...
Plus généralement, prenez un entier p supérieur à 1 et un entier n premier avec p.
Ajoutez 1 à n, puis divisez par p si c'est possible ou ajoutez n,
puis divisez par p si c'est possible ou ajoutez n,
puis divisez par p si c'est possible ou ajoutez n,
...
Obtiendra-t-on 1 ?


Celui qui fuit les casse-tête ne vaut pas un clou.

 #45 - 26-06-2015 22:32:28

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Algorithme vulgaris sipmlex

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

Donc c'est juste lol


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #46 - 28-06-2015 22:59:51

anonyme impair
Visiteur

Algorithme vulgaris siimplex

Bonsoir,

N nombre impair
+1 devient toujours pair
Divisé par 2 nfois jusqu'à 1

 #47 - 29-06-2015 12:40:38

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

algoritjme vulgaris simplex

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

 #48 - 29-06-2015 15:22:02

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3314

Algorithme vulagris simplex

Bien joué ! big_smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #49 - 10-07-2015 09:36:37

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 2953

Algorithme vulgaris smplex

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.

 

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 : 

Dans une course, vous doublez le 42ème, en quelle position êtes-vous ?

Sujets similaires

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