Répondre à la discussion
Affichage des résultats 1 à 28 sur 28

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




  1. #1
    Médiat

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

    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 !

    -----

    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  2. Publicité
  3. #2
    interferences

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

    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
    Ce n'est pas le doute qui rend fou, c'est la certitude.

  4. #3
    Médiat

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

    Bonsoir,

    Je pensais plutôt à "on détermine d'abord le plus petit n puis le plus petit m", mais c'est anecdotique
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse


  5. #4
    contrexemple

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

    Bonsoir,

    n=4, m=32626

  6. #5
    contrexemple

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

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

  7. A voir en vidéo sur Futura
  8. #6
    EauPure

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

    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 ?
    La béatitude est l'attitude de l’abbé : la théorie bleue

  9. #7
    contrexemple

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

    Citation Envoyé par contrexemple Voir le message
    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...

  10. Publicité
  11. #8
    contrexemple

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

    Citation Envoyé par contrexemple Voir le message
    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è.

  12. #9
    Médiat

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

    Bonjour (pas une option sur ce site)

    Citation Envoyé par EauPure Voir le message
    dans (i+1)n, n est il une puissance ou une multiplication
    Si puissance
    C'est la multiplication.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  13. #10
    Médiat

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

    Bonjour,
    Citation Envoyé par contrexemple Voir le message
    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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  14. #11
    contrexemple

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

    Remarque il suffit que pour tout et
     Cliquez pour afficher
    distinct on ait : pour être sûr d'avoir une solution.
    la borne de n donné.

  15. #12
    contrexemple

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

    Citation Envoyé par Médiat Voir le message
    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;

  16. #13
    Médiat

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

    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.
    Dernière modification par Médiat ; 07/04/2015 à 14h58.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  17. #14
    EauPure

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

    Citation Envoyé par contrexemple Voir le message
    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
    Code:
        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
    Dernière modification par EauPure ; 19/04/2015 à 07h45.
    La béatitude est l'attitude de l’abbé : la théorie bleue

  18. #15
    EauPure

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

    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
    La béatitude est l'attitude de l’abbé : la théorie bleue

  19. #16
    EauPure

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

    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
    La béatitude est l'attitude de l’abbé : la théorie bleue

  20. #17
    EauPure

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

    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
    Dernière modification par EauPure ; 19/04/2015 à 17h34.
    La béatitude est l'attitude de l’abbé : la théorie bleue

  21. #18
    EauPure

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

    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
    Dernière modification par EauPure ; 19/04/2015 à 17h50.
    La béatitude est l'attitude de l’abbé : la théorie bleue

  22. #19
    EauPure

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

    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)
    La béatitude est l'attitude de l’abbé : la théorie bleue

  23. #20
    Dynamix

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

    Citation Envoyé par EauPure Voir le message
    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 .

  24. #21
    contrexemple

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

    Citation Envoyé par EauPure Voir le message
    non, ça marche avec n=3 et m=29 (2 nombre premiers)

    trouvé avec la force brute
    Code:
        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

  25. #22
    EauPure

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

    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
    Dernière modification par EauPure ; 19/04/2015 à 18h31.
    La béatitude est l'attitude de l’abbé : la théorie bleue

  26. #23
    Médiat

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

    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 !
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  27. #24
    EauPure

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

    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
    La béatitude est l'attitude de l’abbé : la théorie bleue

  28. #25
    EauPure

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

    Citation Envoyé par Médiat Voir le message
    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 ?
    Dernière modification par EauPure ; 19/04/2015 à 18h56.
    La béatitude est l'attitude de l’abbé : la théorie bleue

  29. #26
    Dynamix

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

    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 .

  30. #27
    EauPure

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

    Citation Envoyé par EauPure Voir le message
    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
    La béatitude est l'attitude de l’abbé : la théorie bleue

  31. #28
    rorodu30

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

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

Discussions similaires

  1. Réponses: 2
    Dernier message: 26/09/2014, 18h01
  2. Réponses: 36
    Dernier message: 02/07/2012, 18h49