Un défi par semaine

Décembre 2017, 4e défi

Le 22 décembre 2017  - Ecrit par  Ana Rechtman Voir les commentaires (12)

Nous vous proposons un défi du calendrier mathématique 2017 chaque vendredi et sa solution la semaine suivante.

Semaine 51 :

Un entier positif est sympathique s’il est multiple du produit de ses chiffres.
Par exemple $312$ est un nombre sympathique puisque $312=52\times (3\times 1\times 2)$. Combien y a-t-il de nombres sympathiques à deux chiffres ?

Solution du 3e défi de Décembre :

Enoncé

La réponse est en deuxième position.

L’énoncé dit que Sophie a nagé plus vite que Marie, que Marie a été plus rapide que Paule et Paule plus rapide que Laura, et enfin que Laura est arrivée avant Anne. Le classement final est donc : Sophie, Marie, Paule, Laura et Anne, donc Marie est arrivée en deuxième position.

Post-scriptum :

Calendrier mathématique 2017 - Sous la direction d’Ana Rechtman, Maxime Bourrigan - Textes : Antoine Rousseau et Marcela Szopos.
2016, Presses universitaires de Strasbourg. Tous droits réservés.

Article édité par Ana Rechtman

Partager cet article

Pour citer cet article :

Ana Rechtman — «Décembre 2017, 4e défi» — Images des Mathématiques, CNRS, 2017

Crédits image :

Image à la une - MAURITUS IMAGES / IMAGEBROKER / J.W. ALKER / PHOTONONSTOP

Commentaire sur 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

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM