Trouver la suite "logique" de 1 - 1 - 9 - 3 - 13

[Médiat]

Bonjour,

Ayant préalablement démontré que la question du titre est idiote (tous les nombres entiers sont mathématiquement acceptables), ce n'est, évidemment, pas la question .

Théorème (dû à Gödel) : pour toutes les suites finies d'entiers naturels U0, U1, ... Uk, il existe n et m deux entiers tels que Ui = m mod (1 + (i+1)n)

Sachant que la démonstration du théorème précédent fait apparaître une solution particulière telle que : n = p!, p > k et pour tout i <= k (p! > Ui)

Ici on trouve la solution Ui = 1 900 914 870 130 mod (1 + (i+1)120)

Question : quelle est la suite de 1 - 1 - 9 - 3 - 13, donnée par la formule Ui = m mod (1 + (i+1)n), telle que le couple (n, m) soit le plus petit (dans l'ordre lexicographique)

Trois remarques :

1. Il existe une solution unique à la question précédente (il en existe (non vide), et l'ordre est un bon ordre)
2. Trouver la réponse au cas ci-dessus n'a d'intérêt que si cela permet de dégager une méthode générale pour trouver la plus petite solution, connaissant une solution particulière, et cela, bien sûr, sans utiliser la force brute, ce que n'importe quel ordinateur peut trouver en quelque secondes.
3. Je connais la réponse à la "Question", mais pas à la remarque 2 ci-dessus.

Merci de n'intervenir que sur le sujet de ce fil tel qu'il est exprimé dans la "Question", tout hors sujet sera détruit !
-----

[interferences]

Bonjour,

Pour résumer, on ne sait pas si une méthode générale "subtile" existe, c'est ça ?
Et sinon, pour clarifier le "dans l'ordre lexicographique" : on détermine d'abord le plus petit m puis le plus petit n right ?

Au revoir

[Médiat]

Bonsoir,

Je pensais plutôt à "on détermine d'abord le plus petit n puis le plus petit m", mais c'est anecdotique

[contrexemple]

Bonsoir,

n=4, m=32626

[A voir en vidéo sur Futura]

[contrexemple]

Sinon j'ai un peu mieux que la force brut.
En testant les n à partir de
avec la troncature entière.

[EauPure]

dans (i+1)n, n est il une puissance ou une multiplication
Si puissance
pour i=1
m mod (1 + (2)n) = 1 -> m=2n + 2
pour i=2
m mod (1 + (3)n) = 1 -> m=3n + 2
2n=3n -> n=0 m=3
pour i=3
m mod (1 + (4)n) = 9 là ça ne marche pas
Explication ?

[contrexemple]

Bonsoir,

n=4, m=32626

Salut Eaupure,

Tu essais tu es obligé de partir de n=3=max{E(a_i/i)+1,i=1..5}, cela ne marche pas.

En revanche vérifie le pour n=4 et m=32626 cela marche et est la plus petite réponse possible.

Ensuite tu t'aide du théorème Chinois, c'est le plus simple...

[contrexemple]

Sinon j'ai un peu mieux que la force brut.
En testant les n à partir de
avec la troncature entière.

Car donc

avec la partie entière par excè.

[Médiat]

Bonjour (pas une option sur ce site)

dans (i+1)n, n est il une puissance ou une multiplication
Si puissance

C'est la multiplication.

[Médiat]

Bonjour,

n=4, m=32626

Non !

Sinon j'ai un peu mieux que la force brut.

Ce n'est que de la force brute avec une majoration, ce n'est pas ce que je cherche.

[contrexemple]

Remarque il suffit que pour tout et

 Cliquez pour afficher

n\leq M

distinct on ait : pour être sûr d'avoir une solution.
la borne de n donné.

[contrexemple]

Bonjour,
Non !

Ce n'est que de la force brute avec une majoration, ce n'est pas ce que je cherche.

Bonjour,

32626 mod 5=1,
32626 mod 9=1,
32626 mod 13=9,
32626 mod 17=3,
32626 mod 21=13;

[Médiat]

Oui, mais non quand même !

D'ailleurs la question n'est pas de trouver la meilleure solution, mais une méthode ou algorithme qui donne efficacement la meilleure solution.

[EauPure]

Salut Eaupure,

Tu essais tu es obligé de partir de n=3=max{E(a_i/i)+1,i=1..5}, cela ne marche pas.

En revanche vérifie le pour n=4 et m=32626 cela marche et est la plus petite réponse possible.

Ensuite tu t'aide du théorème Chinois, c'est le plus simple...

non, ça marche avec n=3 et m=29 (2 nombre premiers)

trouvé avec la force brute

    Open ch & "Suite11.txt" For Output As 1
    ta = Array(1, 1, 9, 3, 13)
    n = 3
    For M = 1 To 100000
    For I = 0 To 4
        If ta(I) <> M Mod (1 + (I + 1) * n) Then
            Exit For
        End If
    Next I
    If I = 5 Then
       Print #1, n
       Print #1, M
       For I = 0 To 4 ' vérification
         Print #1, M & " Mod " & (1 + (I + 1) * n) & "=" & M Mod (1 + (I + 1) * n)
       Next I
     Exit For
    End If
    Next M
    Close #1

29 Mod 4=1
29 Mod 7=1
29 Mod 10=9
29 Mod 13=3
29 Mod 16=13

[EauPure]

J'avais la flemme d'écrire les 5 équations à 2 inconnu mais avec un modulo il faut bien ça
avec ce programme je les lui fait écrire
ta(0)= M Mod (1+1*n)=1
ta(1)= M Mod (1+2*n)=1
ta(2)= M Mod (1+3*n)=9
ta(3)= M Mod (1+4*n)=3
ta(4)= M Mod (1+5*n)=13
Mais je ne sais pas comment les résoudre

[EauPure]

Si on fixe n sachant qu'il est > 0 et le plus petit possible il y a peux de cas et les 2 première équations sont déjà un bon filtre
arrivé à n=3 on a
s(0)= M Mod 4 = 1
s(1)= M Mod 7 = 1
s(2)= M Mod 10 = 9
s(3)= M Mod 13 = 3
s(4)= M Mod 16 = 13
On prend l'équation 4 qui dit que M > ou = 16+13=29 et comme on veux le plus petit c'est bien 29

J'ai quand même utilisé la force brute pour écrire les équations et mon cerveau pour la méthode

[EauPure]

Ce qui est troublant c'est que dans les 2 première équations on trouve M en faisant 4*7+1=29
et
M Mod 4 = M Mod 7

[EauPure]

Est ce que ça marche en général
pour trouver x dans l'équation x mod a = x mod b
x=a*b+1
test avec des valeur au hasard
a=8 b=2
x=17
17 mod 8 = 17 mod 2 = 1
ça marche, mais en tapant l'équation sur google il ne la trouve pas

Merci Media et Contrexemple pour cette belle aventure

[EauPure]

Je l'ai même ajouté à la page de Wikipédia chapitre équivalence comme ça ils pourront la vérifier
http://fr.wikipedia.org/wiki/Modulo_(op%C3%A9ration)

[Dynamix]

Est ce que ça marche en général

Oui mais tu n' obtiens pas toujours la plus petite valeur de x .
Pour 4 et 7 , ça marche .
Mais pas pour 8 et 2 .

[contrexemple]

non, ça marche avec n=3 et m=29 (2 nombre premiers)

trouvé avec la force brute

    Open ch & "Suite11.txt" For Output As 1
    ta = Array(1, 1, 9, 3, 13)
    n = 3
    For M = 1 To 100000
    For I = 0 To 4
        If ta(I) <> M Mod (1 + (I + 1) * n) Then
            Exit For
        End If
    Next I
    If I = 5 Then
       Print #1, n
       Print #1, M
       For I = 0 To 4 ' vérification
         Print #1, M & " Mod " & (1 + (I + 1) * n) & "=" & M Mod (1 + (I + 1) * n)
       Next I
     Exit For
    End If
    Next M
    Close #1

29 Mod 4=1
29 Mod 7=1
29 Mod 10=9
29 Mod 13=3
29 Mod 16=13

Bravo, je suis très étourdie....
Sinon pour faire mieux que la force brut il y a le théorème chinois : http://fr.wikipedia.org/wiki/Th%C3%A...restes_chinois

[EauPure]

oui j'avais remarqué en faisant une erreur que 13 mod 8 = 13 mod 2 = 5
dans ce cas ce serais x=a+b+3 mais est ce général ?
ça marche aussi avec a+b+1
car 11 mod 8 = 11 mod 2=3

Je vous laisse vérifier le cas général

[Médiat]

Bonsoir,

Une précision à nouveau : trouver la solution ici (c'est bien (3, 29)) n'a aucun intérêt, essayer toutes les valeurs de n (par ordre croissant) comprises entre le majorant donné dans le premier message et un minorant trivial pour que les congruences aient une chance de donner les nombres attendus, c'est exactement la force brute : sans aucun intérêt !

[EauPure]

Salut contrexemple, ma réponse était pour Dynamix
en fait a+b+1 ne marche pas pour 4 et 7 car 12 mod 4 = 0 <> 12 mod 7 = 5
ça doit marcher si a et b ont un pgdc
dans ce cas on aurait xmin = a+b-1 ou peut être xmin=max(a,b)+1
pour 8 et 2 xmin=9

[EauPure]

Bonsoir,

Une précision à nouveau : trouver la solution ici (c'est bien (3, 29)) n'a aucun intérêt, essayer toutes les valeurs de n (par ordre croissant) comprises entre le majorant donné dans le premier message et un minorant trivial pour que les congruences aient une chance de donner les nombres attendus, c'est exactement la force brute : sans aucun intérêt !

Bonsoir,

Il faut bien utiliser les 5 équations pour être lié aux 5 occurrences de la suite non ?
J'en utilise que 3 pour un modulo à 2 inconnu, mais effectivement 2 comme filtre des valeurs croissante de n, il y aurait mieux ?

[Dynamix]

L' exemple de 8 et 2 est un cas particulier :
Tout multiple de 8 est multiple de 2 .
Et je te signale que "N mod 2" , ça ne peut faire que 0 ou 1 .

[EauPure]

donc résoudre -13-2n+n²=0
ça ne marche pas pour n=3
car j'égalise un Mmin=14+5n pour l'équation 4 avec un M=(1+n)(1+2n)+1 qui n'est pas forcément min
il faut donc faire
M=(1+5n)*k +13=(1+n)(1+2n)+1
et trouver le bon k

encore 1 erreur dans (1+n)(1+2n)+1 = 1+3n+2n² + 1

1+3n+2n²+1=14+5n
-12-2n+2n²=0 -> n=3
m=14+5n=14+15=29

Cette fois je crois que ça marche et désolé pour le flood, ça montre comment on fait des erreurs en cherchant mais on finis par les trouver

résumé de la méthode
s(0)=s(1)
et dans s(4)
Mmin=1+(1+4)*n+13=14+5*n

[rorodu30]

(1/3)^5 x-13=1/9