22 décembre 2017

12 messages - Retourner à l'article
  • Décembre 2017, 4e défi

    le 22 décembre 2017 à 10:06, par Celem Mene

    Bonjour, j’en ai trouvé cinq :

    11 = (1 * 1) * 11
    12 = (1 * 2) * 6
    15 = (1 * 5) * 3
    24 = (2 * 4) * 3
    36 = (3 * 6) * 2

    Répondre à ce message
  • Décembre 2017, 4e défi

    le 22 décembre 2017 à 10:23, par tilasoldo

    Bonjour, je confirme les 5 trouvés par Celem Mene, avec le petit programme Python :

    count = 0
    for i in range(10, 100):
       a = i % 10
       b = int(i / 10)
       if (a * b) != 0:
           c = i / (a * b)
           if c % 1 == 0:
               count += 1
               print(i, c)
    print(count)
    Répondre à ce message
  • Décembre 2017, 4e défi

    le 22 décembre 2017 à 11:38, par Kamakor

    Soit N un tel nombre. On note d son chiffre des dizaines et u son chiffre des unités.
    On a donc N=10d + u avec 0 <d<10 u<10
    Ainsi u x d divise N => d divise N => d divise 10d + u => d divise u
    Il existe donc un entier naturel k tel que u= k x d
    Ainsi u x d divise N => u divise N => u divise 10d+u => u divise 10d => k x d divise 10d <=> k divise 10
    On a donc u=d , u=2d ou u=5d (et c’est tout car 10d>9)

    Si u=d alors : u x d divise 10d+u <=> d² divise 11d <=> d divise 11 d’où d=1 et u=1 et N=11
    Si u=2d alors : u x d divise 10d+u <=> 2d² divise 12d <=> d divise 6 d’où N=12, N=24 ou N=36
    Si u=5d alors : u x d divise 10d+u <=> 5d² divise 15d <=> d divise 3 d’où N=15

    Au final on a cinq solutions :11, 12, 15, 24 et 36

    Répondre à ce message
  • Décembre 2017, 4e défi

    le 22 décembre 2017 à 12:10, par B !gre

    Comme souvent avec ces défis, j’aime bien me poser la question de leur résolution informatique (en Python en l’occurence). De mon point de vue, ce n’est ni plus ni moins intéressant que la résolution mathématique. Ce qui m’intéresse en particulier est la difficulté calculatoire : quel temps de calcul pour trouver le résultat ? J’ai trouvé ce problème particulièrement adapté. L’idée ici n’est pas de trouver les nombres sympathiques à deux chiffres (je retrouve bien les mêmes que ceux indiqués dans les commentaires précédents), mais de trouver disons tous les nombres sympathiques inférieurs ou égaux à une certaine borne N (ou les compter). J’ai pu dénombrer par exemple tous les entiers sympathiques non nuls à au plus 7 chiffres en 5s sur un ordinateur standard (il y en a 1223), sachant que mon code initial (plutôt naïf) mettait plutôt dans les 30 secondes, ou ceux à au plus 8 chiffres (3174) en 1 minute.

    Quelqu’un fait mieux ?

    P.S. : Je peux copier mon code si certains sont intéressés.

    Répondre à ce message
    • Décembre 2017, 4e défi

      le 22 décembre 2017 à 12:33, par Celem Mene

      Oui, ça paraît beaucoup. En c, sans me soucier de son efficacité, mon code fait 0.326« jusqu’à 7 chiffres et jusqu’à 8 en 3.236 ». Fais-voir ton code.

      Répondre à ce message
      • Décembre 2017, 4e défi

        le 22 décembre 2017 à 13:22, par B !gre

        Je ne serais pas étonné que ce soit dû principalement à la lenteur intrinsèque de Python... mais je veux bien ton avis ! Pour les sympathiques jusqu’à 7 chiffres : nb_sympathiques(10**7).

        def div_par_prod(N):
           "Renvoie True si N est divisible par le produit de ses chiffres"
           q = N
           while N > 0:
               N, c = divmod(N, 10)
               if not c: return False
               q, r = divmod(q, c)
               if r: return False
           return True

        def nb_sympathiques(N):
           "Compte le nombre d'entiers sympathiques < N"
           c = 0
           for i in range(1, N):
               if div_par_prod(i):
                   c += 1
           return c
        Répondre à ce message
        • Décembre 2017, 4e défi

          le 22 décembre 2017 à 15:49, par Celem Mene

          Ca me semble pourtant bien correct. Mais ça met 1.5 x plus de temps. Pour info voici le mien :

          /*
          Compilation : gcc -std=c99 -Wall -Wextra -pedantic sympathique.c -o sympathique
          */

          #include <stdio.h>
          #include <stdlib.h>

          int sympathique (unsigned long long, unsigned long long *) ;

          int sympathique (unsigned long long n, unsigned long long *p)

          unsigned long long m = n ;
          *p = 1 ;

          while (m && *p)

          *p *= m % 10 ;
          m /= 10 ;

          if (*p == 0)
          return 0 ;
          else
          return n % *p == 0 ? 1 : 0 ;

          int main (int argc, char *argv[])

          unsigned long long max, min, n, c = 0, p ;

          if (argc == 1)
          printf (« Utilisation : %s [minimum] maximum.\n », argv[0]) ;
          else
          min = (unsigned) atoll (argv[1]) ;

          max = argc > 2 ? (unsigned) atoll (argv[2]) : min ;
          n = min ;

          while (n <= max)

          if (sympathique (n, &p))

          c++ ;
          printf ("%llu %llu %llu\n", c, n, p) ;

          n++ ;

          return EXIT_SUCCESS ;

          Répondre à ce message
        • Décembre 2017, 4e défi

          le 23 décembre 2017 à 14:42, par Niak

          Rien d’anormal, C/C++ est un langage compilé (en code machine directement exécuté par le processeur) réputé pour sa performance (car d’assez « bas niveau ») tandis que Python est un langage interprété (compilé à la volée lors de l’exécution en bytecode exécuté par une machine virtuelle, ce qui simplifie pour le programmeur les questions de gestion de la mémoire, de portabilité, etc, et offre une grande flexibilité). En contrepartie les performances ne sont pas comparables. Néanmoins il existe un interpréteur Python beaucoup plus rapide (qui compile à la volée en code machine) nommé PyPy.

          Répondre à ce message
    • Décembre 2017, 4e défi

      le 23 décembre 2017 à 14:50, par Niak

      Si ces aspects algorithmiques de la résolution de problèmes mathématiques vous intéressent et que vous ne connaissez pas Project Euler, alors vous pourriez y jeter un œil, ça devrait vous plaire !

      Répondre à ce message
  • Décembre 2017, 4e défi

    le 23 décembre 2017 à 22:55, par Jean-Paul

    J’ai aussi fait le test en C++ , d’abord en utilisant la méthode directe ; puis avec une approche récursive, beaucoup plus rapide. Les temps obtenus pour 7, 8 et 9 chiffres :

    Méthode directe : .23, 2.3 et 23.4
    Méthode récursive : .07, .55 et 4.8

    Dans la méthode récursive, il y a un niveau d’appel pour chaque chiffre et le calcul du produit des premiers chiffres est passé au niveau suivant, ce qui réduit de beaucoup le nombre de calculs.

     
    #include    <iostream>
    using namespace std;

    void f(long long, long, int);

    int main(int ac, char *av[])
    {
       int nch = atoi(av[1]);
       
       for (int i = 1; i <= nch; i++) f(0, 1, i);
       
       return 0;
    }  

    void f(long long n, long p, int niveau)
    {
       n *= 10;
       
       if (niveau == 1)
       {
           for (int i = 1; i <= 9; i++) if ((n+i) % (p*i) == 0) cout << n + i << endl;
       }
       else
       {  
           for (int i = 1; i <= 9; i++) f(n + i, p * i, niveau - 1);
       }  
    }


    Pour référence, la méthode directe :

     
    #include    <iostream>

    using namespace std;

    bool sym(long n);

    int main(int ac, char *av[])
    {
       long min = atoi(av[1]);
       long max = atoi(av[2]);
       
       for (long n = min; n < max; n++) if (sym(n)) cout << n << endl;
       
       return 0;
    }

    bool sym(long n)
    {  
       long c = n;
       long p = 1;
       
       do  
       {
           p *= c % 10;
           c /= 10;
       } while (c && p);
       
       return p && (n % p == 0);
    }
    Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.