Curriculum and Labs for Engineering Education

cancel
Showing results for 
Search instead for 
Did you mean: 

Challenge mathématique #33 : Un terme dont le rang est en or

Avez-vous encore des cheveux après ces défis ?


Comme le précédent défi a été assez suivi, je propose de continuer dans le même esprit  simple

Pour Mai, toujours un "Livre de programmation LabVIEW" de plus de 400 pages de chez DUNOD à gagner.

Il suffit de m'envoyer à emmanuel.roset@ni.com votre solution avant le 31 mai, sous forme d'un VIen utilisant le VI Joint comme départ pour les valeurs.


Voici le challenge :

La suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent :

  • elle commence par les termes 0 et 1 ;
  • le 3e terme est donc 0+1 = 1 ;
  • le 4e terme est donc 1+1 = 2 ;
  • et ainsi de suite : 3, 5, 8, 13, 21...


Défi :

Trouvez avec LabVIEW le premier terme de la suite de Fibonacci dont la somme des chiffres est égale au nombre fourni en entrée.

En entrée vous avez un nombre entier N entre 1 et 100, en sortie donnez le rang du terme T et le nombre de la solution S


Exemple :

Si le nombre fourni en entrée N est 24 alors la solution S est 987, T est le 17e terme (en comptant 0) puisque 9+8+7 = 24

Donc lequel est pour 28 ? 80 ou tout N inférieur à 100 ?


Attention les manipulations peuvent générer des grands chiffres d’entiers

Bon petit défi

Comments
Didier_Bleses
Member
Member
on

Code envoyé

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

Bonjour emmanuel,

Petite question:

N=24 donne S=987 ... ok.

Mais je vois que tu proposes un DBL pour sortir la résultat "S".

Le soucis est qu'avec un DBL il n'est pas possible de sortir avec exactitude le résultat "S" pour une suite de Fibonacci dont le nombre de termes dépassent 79:

voici:


F(79) = 8944394323791464 (ok, correct, c'est bon sur DBL)

mais

F(80) = 14472334024676220 (faux ! ... le résultat exact est 14472334024676221

à partir de n>79 (nombre de termes) un DBL est insuffisant. Et plus n augmente, et plus l'erreur est importante.

Personnellement, j'utilise un Tableau de U32 pour exprimer les très grands nombres (exactitude absolue à l'infini)

De toute façon au delà de n>79, un DBL est également insuffisant pour contenir avec exactitude tous les "chiffres" dont il faut ensuite faire la somme.

Qu'en penses-tu ?

Puis-je "sortir" S avec un Tableau de U32 ?


emmanuel-fr
Member
Member
on

Tout a fait exact Ouadj ! vous êtes libre de changer la sortie en U64 si besoin . C'est pour ca que j'ai ajouté la petite phrase à la fin pour mettre en garde et vous avez parfaitement rempli la mission de vérification

D'ailleurs j'ai reçu des codes (déjà) et il faut faire des essais et concentrer ses efforts sur la zone de 80 à 99 car on peut avoir des surprises pas évidentes à vérifier.

Cela fait un rappel que dans un code LabVIEW "classique" il faut faire attention aux dépassements sinon on ne s'en rend pas compte que le résultat est faux.

sabri.jatlaoui
Active Participant
Active Participant
on

Bonjour Emmanuel,

Code envoyé.

Sabri JATLAOUI - Certified LabVIEW Architect - Certified LabVIEW Developer
ouadji
Trusted Enthusiast
Trusted Enthusiast
on

Je défie quiconque de me trouver une réponse pour N=6    Ceci dit, en passant, même un U64 est totalement insuffisant.

Cette cible pour N=6 peut très bien se trouver très très loin ... par une addition des deux précédents qui auront comme résultat un nombre comportant une multitude de zéro et dont la somme des chiffres fera 6. Je rassure tout le monde, le PC a tourné la moitié de la nuit jusqu'à un rang supérieure à 2E+6 ... et je n'ai jamais trouvé d'écho pour N=6. Mais rien ne permet d'affirmer que cette cible (pour N=6) n'existe pas. Un petit challenge pas mal intéressant. Bravo Emmanuel.

sabri.jatlaoui
Active Participant
Active Participant
on

Salut Ouadji, avec N=6 ta suite de Fibonacci donne [0,1,1,2,3,5,8] donc un tableau de 7 éléments et dedant je ne vois pas mon N.

Ou je rate quelque chose?

Sabri JATLAOUI - Certified LabVIEW Architect - Certified LabVIEW Developer
ouadji
Trusted Enthusiast
Trusted Enthusiast
on

N ... c'est l'addition des chiffres (ou alors je n'ai rien compris)

exemple : N=24

il faut trouver un nombre faisant partie de la suite de Fibonacci, qui, si tu en additionnes les chiffres constitutifs, te donneras 24.

Ce nombre existe ... en effet, au rang 17 de la Suite, tu as le nombre 987 ... et 9+8+7 = 24 ... bingo

input : 24

output : 17 - 987

Moi, je pose N=6

Donc ... peux-tu me trouver un nombre faisant partie de la suite de Fibonacci, qui, si tu en additionnes les chiffres séparément, te donneras un résultat de 6.


sabri.jatlaoui
Active Participant
Active Participant
on

100% d'accord avec toi mais pour moi si N est le nombre total de termes, donc si N=6  ta suite de Fibonacci s'arrête à 8. Mais il est vrai que ce n'est pas spécifié dans L'énoncé.

Sabri JATLAOUI - Certified LabVIEW Architect - Certified LabVIEW Developer
ouadji
Trusted Enthusiast
Trusted Enthusiast
on

Pour moi .. non ... N ne représente pas un nombre de termes ... c'est le résultat d'une addition.

Ce sera plutôt " T " alors ...

N=24 ... ça , c'est la "question"

Réponse : S=987 et T=17

car 987 est en 17eme position dans la suite. (le 1er élément, soit "0" est en position 1)

Pour moi, T représente "l'index" de S et aussi, en corollaire, le nombre d'élément de la suite pour arriver à S.

autre exemple :

question : N =100

réponse : S = 83621143489848422977  T = 98 (ce nombre est le 98eme de la suite)

Parceque : (8+3+6+2 ......+9+7+7) = 100

sabri.jatlaoui
Active Participant
Active Participant
on

Du coup quand est ce que tu arrêté ta suite de Fibonacci ? Ça n'est pas défini dans l'énoncé. N est le résultat recherché,  mais peut aussi être le nombre de terme. Dans ce cas là le nom aurait été bien choisi.

Sabri JATLAOUI - Certified LabVIEW Architect - Certified LabVIEW Developer
ouadji
Trusted Enthusiast
Trusted Enthusiast
on

Emmanuel ... 

on a besoin de toi pour éclaircir la situation ...

(voir les 4/5 messages précédents.)

[edit]

@sabri.jatlaoui : "N est le résultat recherché ... "

à mon sens, N n'est pas le résultat recherché, c'est "la donnée d'entrée".

Le résultat recherché est le 1er nombre de la Suite dont l'addition interne des chiffres donnent N.

ou alors ... je suis complètement dans le mur et je n'ai rien compris. (toujours possible)

@sabri.jatlaoui : "quand est ce que tu arrêté ta suite de Fibonacci ?"

Quand j'ai trouvé le 1er nombre de la suite qui correspond à l'énoncé ..

et si je ne trouve pas ... chaque développeur gère "la fin de recherche" quand il le désire (la limite est la mémoire du PC)

Je laisse à Emmanuel le soin de confirmer ou clarifier tout ceci.

Les divergences de vue montre qu'il est nécessaire de préciser l'énoncé.

[/edit]

Nico_EMC
Member
Member
on

Bon, on arrive effectivement assez vite à dépasser les U64. Je crois qu'il va falloir ressortir les grands chiffres (cf challenge 4!!)

Bon courrage

AFLAMENT
Member
Member
on

Bonjour,

Pardon mais si N=1 alors T=2 (terme d'initialisation) ou 3?

BR

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

0,1,1,2,3,5,8 ...

N=1 ... quel est le 1ere nombre de la suite dont la somme interne des chifres vaut 1 ? La réponse ?...

Il faut d'abord définir la position attribuée à "0". L'exemple d'emmanuel (dans l'énoncé) dit :

" Si le nombre fourni en entrée N est 24 alors la solution S est 987, T est le 17e terme "

Dans son exemple Emmanuel donne donc à "0" la position 1.

Pour moi, la réponse serait donc:

N=1 >> S=1 et T=2   car le 1er "1" est le 2eme terme de la suite (avec 0 en position 1)

PS:

Le tout ... sous réserve d'avoir "bien compris".

Voir les messages précédents et ma demande à Emmanuel de clarifier définitivement tout ceci.


lulu44
Active Participant
Active Participant
on

code envoyé

Cordialement
L.MICOU
lulu44
Active Participant
Active Participant
on

Bonjour,

dans l'énoncé d'emmanuel:

" La suite de Fibonacci est une suite d'entiers dans laquelle chaque terme est la somme des deux termes qui le précèdent :

  • elle commence par les termes 0 et 1 ;
  • le 3e terme est donc 0+1 = 1 ;
  • le 4e terme est donc 1+1 = 2 ;"

pour moi on a alors N = 1, S = 1 et T = 3

et pour N = 2, S = 2 et T = 4 ...

Cordialement
L.MICOU
adcpc
Member
Member
on

Bien qu'il existe peut-être une démonstration pour prouver qu'il n'est pas nécessaire de calculer jusqu'à obtenir S avec des milliers de digits, est-ce qu'il est possible de fixer un limite maximale pour le nombre de termes à calculer ?

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

@lulu44 :

dans la mesure où l'on considère que les 2 premiers termes "0,1" sont les termes "d'initialisation",

et que la Suite commence réellement au terme 3 (le 2eme 1)

alors oui, je suis d'accord avec toi, soit :  N = 1, S = 1 et T = 3

AFLAMENT
Member
Member
on

Ok donc T0 et T1 sont des termes d'initialisation donc pour N=1 T=3

Eh l'admin tu peux affirmer ou confirmer s'il te plait merci?

emmanuel-fr
Member
Member
on

Bonjour à tous et à ouadj !

Je suis en congés avec un accès limité au wifi mais je suis de près les échanges passionnés 😉

Bon alors ouadj à tout à fait raison dans tous les échanges. N est le chiffre qui correspond à la somme des chiffres composant l'un des éléments de la suite. Donc quand on cherche cette correspondance on s'arrête dès la première valeur trouvée. On remarque en faisant le tableau des additions des chiffres de fibonnacci séparément que parfois ce nombre additionné se répète plusieurs fois...

Impossible donc de savoir quand s'arrêter autrement que lorsque la première égalité est trouvée.

Pour certaines valeurs comme le 6 on ne voit pas de correspondance au début et aussi dans les 100 premiers, mais rien ne dit que plus loin pourquoi pas meme si intuitivement on imagine que l'on tombe sur des nombres additionnés de plus en plus grand et que statistiquement il y aura moins de chance. Par exemple on pourrais tomber sur 111000102...

Pour les valeurs au dessus de 80 les U64 ne suffisent pas car on dépasse les 2e19 recommandés et on plafonne sur les 2e19 avec des dépassements qui tournent en rond sur des valeurs fausses. Normalement il faut utiliser des éléments d'addition d'un challenge précédent sur les grands nombres pour réussir à dépasser cette limite.

C'est pas grave pour les quelques codes déjà reçus en U64, merci à vous meme si le piège se referme :-)) Le code final n'est pas plus compliqué, mais juste il faut utiliser une addition qui n'est pas limitée en taille.

Pour les valeurs initiales oui effectivement au début c'est invariable. Donc le premier terme pour 1 est T=3. Mais c'est un cas particulier. Question tout à fait justifiée. Merci 🙂

Merci à tous

C'est beau les chiffres on découvre tout le temps des choses magiques

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

Merci Emmanuel pour cette clarification,

Pour N=6 (et d'autres) ... ... la suite de Fibonacci est divergente et tend vers l'infini. Comme Emmanuel l'a très bien dit, rien n'interdit (au "hasard" des additions, très loin dans la suite) qu'un nombre ait une somme interne égale à 6. En tout cas, pour exclure "6" il faudrait pouvoir démontrer l'impossibilité de son existence ... et là, bonne chance au matheux pour démontrer ce genre de chose ... surtout sur base du postulat de la somme interne des chiffres. Pour que tout le monde économise sur la facture d'électricité ... ... j'ai testé ce fameux "6" jusqu'au terme de rang 2E+7 (oui, 20 millions, toute une nuit) ... et je n'ai pas eu d'écho positif. Cela fait quand même un nombre décimal de plus de 4E+6 digits. Pour ceux qui veulent "tester" leur code, il y a ceci . (Attention, au delà de 10.000 cela commence à devenir lent). Je suis d'accord avec Emmanuel .. il y a quelque chose de fascinant avec les nombres (en particulier les suites, je trouve)

BBrice
Member
Member
on

Code envoyé

Didier_Bleses
Member
Member
on

J'ai pensé que la suite de Fibonacci pouvait avoir un schéma répétitif et voila ce que j'ai trouvé :
- Une suite des unités se reproduit tous les 60 termes, c'est à dire que pour tout terme Tn on trouve un terme Tn+60 qui à le même dernier chiffre (unité).
exemple :
T3=1  => T63= 4052739537881
T4=2  => T64= 6557470319842
T5=3  => T65=10610209857723
       
- De même, une suite des 2 derniers chiffres (unités et dizaines) se reproduit tous les 300 termes, c'est à dire que pour tout terme Tn on trouve un terme Tn+300 qui a les mêmes 2 derniers chiffres.
T3=01 => T303= 581811569..9401 =>T603=289117532..8801
T4=02 => T304= 941390895..9202 =>T604=467801993..8402
T5=03 => T305=1523202464..8603 =>T605=756919526..7203

- pour les 3 derniers chiffres (unités, dizaines et centaines), on monte plus haut Tn =>Tn+3000:
T3=001 => T3003=107500634...94001 =>T6003=987033239...88001
T4=002 => T3004=173939680...92002 =>T6004=159705332...84002
T5=005 => T3005=281440315...86003 =>T6005=258408656...72003

Pour les milliers on cherchera une répétition à Tn+30000.
Honnetement je ne suis pas allé plus loin mais j'image qu'on passe à Tn+300 000 pour la répétition des 4 derniers... (45 minutes de calcul pour les 2 premiers millions de termes...)

Ensuite j'ai remarqué un autre schéma répétitif apparaitre :
T63= 4052739537881 =>T603=289117532..8801 =>T6003=987033239...88001
T64= 6557470319842 =>T604=467801993..8402 =>T6004=159705332...84002
T65=10610209857723 =>T605=756919526..7203 =>T6005=258408656...72003

J'imagine qu'on peut trouver encore pleins d'autres schémas répétitifs du même genre à de plus hauts niveaux.

Je suis donc convaincu que N=6 n'existe pas quelque soit le terme de la suite.

En effet ouadji, les nombres sont fascinants.

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

@ Didier_Bleses : " 45 minutes de calcul pour les 2 premiers millions de termes... "

Tu calcules les termes et tu les mémorises (dans un Tableau)

ou ... tu les calcules simplement un à un sans les mémorier ?

ouadji
Trusted Enthusiast
Trusted Enthusiast
on
Didier_Bleses
Member
Member
on

Non je n'ai pas mémorisé les nombres. J'ai essayé d'une façon brut et j'avais un problème de mémoire vers 200 000 termes.

Ils sont calculés les uns après les autres, en ne mémorisant que les 2 derniers.

Au début du challenge, pour voir ou je mettais les pieds, j'ai fait une évaluation de N en fonction des termes T.

Ca m'a donné ces 2 graphs. Le premier N est la sommes des chiffres de Fibonacci. Pour le 2ieme graph, N est le temps cumulé en secondes pour tout calculer.

fibonacci.gif

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

ok. Tu ne gardes que les 2 derniers, le minimum pour pouvoir calculer le suivant, compris.

Quand tu parles de 45 min pour les 2E+6 premiers termes ... ton code calcule chaque terme par addition des 2 précédents (bien entendu) ... mais ton code calculte-t-il aussi (pour chaque terme) la somme interne ? ou ... as-tu enlevé cette partie du code temporairement ? Autrement dit ... 45min / 2E+6 termes ... c'est uniquement "les termes" ou "termes + somme interne" ?

Tolcim10
Member
Member
on

Code envoyé

Didier_Bleses
Member
Member
on

Je calcul le nombre de Fibonacci et sa somme N.

Je viens de relancer mon code, 2722s pour 2 millions de termes + tableau des sommes qui sont ensuites mise sous graph :

fibonacci2.gif

Nico_EMC
Member
Member
on

Code envoyé.

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

@ Didier_Bleses :

J'ai regardé "ton image" et je confirme :

longueur = 417976  et  le nombre = 13803925144 .... 626

Le problème, c'est que pour obtenir les mêmes résultats que toi, je dois aller jusqu'au terme n° 2.000.002 (et pas 2.000.000).

N'aurais-tu pas (peut-être) oublié de comptabiliser les 2 premiers termes (le "0" et le "1" de départ) ?

(en n'oubliant pas que le tout premier terme, le "0", est le terme n°1)

Quand tu fais une recherche sur N=24 ... as-tu bien S=987 et surtout T=17 ?

autre exemple (chez moi) :

le terme n° 1000 donne : nombre 4346 ... 8875  et  longueur = 209

Qu'en penses-tu ?

Didier_Bleses
Member
Member
on

En effet, le 0 et 1 d'origine ne sont pas ajoutés au compteur sur l'image. Ils le sont dans le code réponse au challenge

Par contre le terme numéro 1000 donne 268638100244853593861467272021429 ...4626, tu as donné le terme 1001, sauf erreur de ma part.

Terme 1 : F[0]=0

Terme 2 : F[1]=1

Terme 3 : F[2]=1

Terme 4 : F[3]=2

...

Terme 17 : F[16]=987

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

Parfaitement exact ... j'ai donné le terme 1001 (et pas le 1000) ... il état tard 

Le terme n°1000 (avec le "0"= n°1) est effectivement 2686 .... 4626.

yyyyyy.png

bon ... je crois que là ... on est synchro 

Bonne journée Didier.

ALoa
Member
Member
on

code envoyé

Bilsix
NI Employee (retired)
on

Mais du coup, que fait-on pour ce fameux N=6 ? On envoi le code réponse comme ça, avec cette petite tare ?

Ca me gêne d'envoyer un code qui, possiblement, peut faire tourner dans le vide à l'infini un thread de l'utilisateur...

Bilsix.
Didier_Bleses
Member
Member
on

Il n'y a pas que N=6.

Le probleme existe pour les N : 6, 11, 12, 13, 15, 16, 18, 25, 26, 32, 36, 38, 39, 40, 42, 45, 47, 49, 50, 56, 57, 60, 63, 70, 71, 74, 75, 76, 81, 83, 88, 92, 96, 99.

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

6,11,12,13,15,16,18,25,26,32,36,38,39,40,42,45,47,49,50,56,57,60,63,70,71,74,75,76,81,83,88,92,96,99.

Je confirme, j'ai exactement les mêmes N "sans solution".

ça, c'est uniquement pour N =< 100 ... Les N sans solutions (apparentes) sont également très nombreux au delà de 100.

@ Bilsix : alors que faire ?

à toi de stopper la recherche après un certain temps (ou rang maximum dans la Suite)

... et de "déclarer" qu'aucune solution n'a été trouvée.

Sebastien_D
Member
Member
on

Code envoyé !

emmanuel-fr
Member
Member
on

Bonjour,

Voici les codes que j'ai trouvé dans ma boite email en cours. j'espère que tout le monde s'y trouve, sinon faites moi un signe ! il reste du temps

J'ai pas encore vérifié les valeurs. En tout cas bravo pour les réflexions sur les chiffres sans solutions et les dépassements, etc..

1 - Bleses_Permier terme
2 - Permier terme_sabri.vi
3 - adcpc_ch32.vi
4 - ch33_lulu44.vi
5 - Permier terme_BBrice.vi
6 - ouadji - Ch33.zip
7 - Tolcim10-Défi33.rar
8 - Nico_EMC_Permier terme.vi

9 - Sebastien_D_CH33.vi

10 - ALoa_ch33.vi
didje007
Active Participant
Active Participant
on

code envoyé

Alice_M
Member
Member
on

Code envoyé

Cisco
Active Participant
Active Participant
on

Code envoyé

Francis M
emmanuel-fr
Member
Member
on

Bonjour,

Voici les codes analysés et les noms des participants, regardez si vous êtes bien dans la liste et que je ne vous ai pas oublié dans les emails (recus avant le 31 mai). Nous ferons le tirage au sort suivant les chiffres du loto de lundi soir. Modalités a suivre pour gagner le livre LabVIEW.

Il y a 3 codes qui utilisent la méthode U64 donc qui ont des dépassements sur les valeurs élevées. Ils restent tout a fait fonctionnels et tous les codes seront mis en ligne ensuite car il y a pas mal de variations sur les moyens employés pour arriver aux résultats qui peuvent donner des astuces !

1 - Bleses_Permier termeCode ok
2 - Permier terme_BBrice.viCode ok
3 - ouadji - Ch33.zipCode ok (et belle face-avant)
4 - Tolcim10-Défi33.rarCode ok
5 - Nico_EMC_Permier terme.viCode ok
6 - Sebastien_D_CH33.viCode ok
7 - ALoa_ch33.viCode ok
8 - Permier terme Didje 007.viCode ok
9 - Alice_M_ch33.viCode ok
10 - Permier terme_cisco v2.viCode ok


Phi_Bour_Permier terme.viFonctionne mais pas valeurs (90, 100)
Permier terme_sabri.viFonctionne mais pas valeurs (90, 100)
ch33_lulu44.viFonctionne mais pas valeurs (90, 100)
emmanuel-fr
Member
Member
on

Bonjour,

Je n'ai pas pu définir les modalités pour le loto de Lundi par empêchement. Etant donné que que j'ai pas eu de mail pour réclamation d'un code non recu depuis, on confirme le nombre de 10 participants. Le résultat se fera sur le loto de ce soir, on prendra le numéro chance pour départager c'est plus simple.

Bonne chance

emmanuel-fr
Member
Member
on

Voici le résultat du loto d'hier soir

date_de_forclusionboule_1boule_2boule_3boule_4boule_5numero_chance
08/08/2016456849339

La gagnante est.... le numéro chance 9 : Alice_M

Bravo et merci vous tous pour vos participations et nombreux échanges, voir mini challenges internes...

Code en pièce jointe en haut dans le sujet

Contributors