Enigme Suite autoalimentée @ Prise2Tete

nodgim · #1

Bonjour @ tous.

Une petite énigme pas méchante, juste pour entretenir les neurones aux calculs simples....

Soit la suite u(n+1) = u(n) + s(u(n)) - [u(n)/s(u(n))]

avec s(u(n)) = somme des chiffres de u(n)
[..]: partie entière. u(0) est un entier naturel.

1) Donner la suite pour u(o) = 2017.

2) Donner, s'ils existent, les u(0) pour lesquels u(1) = u(0). S'il y en a une infinité ou un nombre fini, donner la justification.

3) Trouver, en justifiant, et s'il existe, le plus grand u(0) pour lequel u(1) > u(0).

Bon amusement

Ebichu · #2

Bonjour,

1) La suite est globalement décroissante, même si pour quelques valeurs, elle remonte (le premier exemple est u(36)=299 et u(37)=305). À partir de u(68), elle est constante égale à 71.

2) Ce sont 1 ; 52 ; 71 ; 81 ; 109 ; 128 ; 147 ; 175 ; 259 ; 268 ; 296 ; 379 ; 499. On prouve la finitude par exemple en remarquant que si on prend pour u(0) un nombre à 5 chiffres, s(u(0)) vaut au plus 45, et 45 < [10000/45], d'où s(u(0)) < [u(0)/s(u(0))], et u(1)<u(0). Le même raisonnement tient pour les nombres à k chiffres avec k>5. Il reste à tester les nombres inférieurs à 10000, et la question est réglée (on peut d'ailleurs éliminer une partie de ces nombres avec un raisonnement similaire, en considérant des ensembles plus restreints que "les nombres à k chiffres").

3) Le raisonnement précédent s'applique. En testant les nombres inférieurs à 10000, le plus grand qui convient est 399 (dont l'image est 401).

enigmatus · #3

Bonjour,
1) u68 = u69 = 71

Code:

2) Résultat expérimental, je n'en ai pas trouvé d'autres jusqu'à u0 = 10 000 000

Code:

3) Résultat expérimental, je n'en ai pas trouvé d'autres jusqu'à u0 = 10 000 000

Code:

u0 = 399
u1 = 401

golgot59 · #4

Salut !

1) u(0)=2017 et s(u(n))=10
u(1)=2017+10-[2017/10]=2027-201=1826
u(2)=1826+17-[1827/17]=1843-107=1736 puis
1651; 1537; 1457; 1389; 1344; 1244; 1142; 1008; etc; 71; 71; 71

2) d'abord u(0) = 71 est une réponse évidente d'après 1)
Il y a aussi 1; 52; 81; 109; 128; 147; 175; 259; 268; 296; 379; 499

Si on veut que qu'un nombre le plus grand possible ait pour suivant lui même il faut maximiser S(u(n)).
à 5 chiffres : S(u(n)) max = 5*9=45
u(n+1)=u(n)+S(u(n))-(u(n)/S(u(n)))
si u(n+1)=u(n) : S(u(n)) = E(u(n)/S(u(n)))
Donc si on oublie la partie entière pour simplifier le calcul : u(n)=S(u(n)²<45²=2025 qui n'est pas un nombre à 5 chiffres. Inutile évidemment de prendre un nombre à plus de 5 chiffres.
A 4 chiffres, on trouve pour max : 4*9=36 et on obtient un nombre à 4 chiffres qui doit être inférieur à 1296. Ma liste précédente me semble du coup complète...

Désolé pour ces explications très loin de la rigueur attendue...

3)Le plus grand que je trouve est 399 qui est suivi par 401...

nodgim · #5

Que des bonnes réponses, bravo @ tous ! Mais je ne suis pas surpris.

Enigmatus ne fournit pas vraiment de justification, celle-ci n'est pas bien méchante.

Personne ne m'a dit qu'il avait trouvé tous les nombres "stationnaires" à la main. On peut pourtant le faire sans trop se casser la tête....

scarta · #6

Hello,

pour 2017, je vais pas mettre toutes les valeurs, mais ça boucle sur 71 après 69 itérations.

Pour les questions 2 et 3 (en bloc): pour avoir u(n+1) >= u(n) il faut impérativement avoir s(u(n)) >= [u(n)/s(u(n))]
Autrement dit, u(n) <= s(u(n))² + s(u(n))-1
L'égalité est obtenue pour u(n) compris entre s(n)² et la limite ci-dessus.

De là, on peut donc tout sortir assez facilement... en se basant sur s(U(n))

Pour S(U(n)) = 1, on a u(n) inférieur ou égal à 1, et supérieur ou égal à 1 pour l'égalité.
----- Solutions u(1) > u(0): --
----- Solutions u(1) = u(0): {1}
Pour S(U(n)) = 2, on a u(n) inférieur ou égal à 5, et supérieur ou égal à 4 pour l'égalité.
----- Solutions u(1) > u(0): {2}
----- Solutions u(1) = u(0): --
Pour S(U(n)) = 3, on a u(n) inférieur ou égal à 11, et supérieur ou égal à 9 pour l'égalité.
----- Solutions u(1) > u(0): {3}
----- Solutions u(1) = u(0): --
Pour S(U(n)) = 4, on a u(n) inférieur ou égal à 19, et supérieur ou égal à 16 pour l'égalité.
----- Solutions u(1) > u(0): {4,13}
----- Solutions u(1) = u(0): --
Pour S(U(n)) = 5, on a u(n) inférieur ou égal à 29, et supérieur ou égal à 25 pour l'égalité.
----- Solutions u(1) > u(0): {5,14,23}
----- Solutions u(1) = u(0): --
Pour S(U(n)) = 6, on a u(n) inférieur ou égal à 41, et supérieur ou égal à 36 pour l'égalité.
----- Solutions u(1) > u(0): {6,15,24,33}
----- Solutions u(1) = u(0): --
Pour S(U(n)) = 7, on a u(n) inférieur ou égal à 55, et supérieur ou égal à 49 pour l'égalité.
----- Solutions u(1) > u(0): {7,16,25,34,43}
----- Solutions u(1) = u(0): {52}
Pour S(U(n)) = 8, on a u(n) inférieur ou égal à 71, et supérieur ou égal à 64 pour l'égalité.
----- Solutions u(1) > u(0): {8,17,26,35,44,53,62}
----- Solutions u(1) = u(0): {71]
Pour S(U(n)) = 9, on a u(n) inférieur ou égal à 89, et supérieur ou égal à 81 pour l'égalité.
----- Solutions u(1) > u(0): {9,18,27,36,45,54,63,72}
----- Solutions u(1) = u(0): {81}
Pour S(U(n)) = 10, on a u(n) inférieur ou égal à 109, et supérieur ou égal à 100 pour l'égalité.
----- Solutions u(1) > u(0): {19,28,37,46,55,64,73,82,91}
----- Solutions u(1) = u(0): {109}
Pour S(U(n)) = 11, on a u(n) inférieur ou égal à 131, et supérieur ou égal à 121 pour l'égalité.
----- Solutions u(1) > u(0): {29,38,47,56,65,74,83,92,119}
----- Solutions u(1) = u(0): {128}
Pour S(U(n)) = 12, on a u(n) inférieur ou égal à 155, et supérieur ou égal à 144 pour l'égalité.
----- Solutions u(1) > u(0): {39,48,57,66,75,84,93,129,138}
----- Solutions u(1) = u(0): {147}
Pour S(U(n)) = 13, on a u(n) inférieur ou égal à 181, et supérieur ou égal à 169 pour l'égalité.
----- Solutions u(1) > u(0): {49,58,67,76,85,94,139,148,157,166}
----- Solutions u(1) = u(0): {175}
Pour S(U(n)) = 14, on a u(n) inférieur ou égal à 209, et supérieur ou égal à 196 pour l'égalité.
----- Solutions u(1) > u(0): {59,68,77,86,95,149,158,167,176,185,194}
----- Solutions u(1) = u(0): --
Pour S(U(n)) = 15, on a u(n) inférieur ou égal à 239, et supérieur ou égal à 225 pour l'égalité.
----- Solutions u(1) > u(0): {69,78,87,96,159,168,177,186,195}
----- Solutions u(1) = u(0): --
Pour S(U(n)) = 16, on a u(n) inférieur ou égal à 271, et supérieur ou égal à 256 pour l'égalité.
----- Solutions u(1) > u(0): {79,88,97,169,178,187,196}
----- Solutions u(1) = u(0): {259,268}
Pour S(U(n)) = 17, on a u(n) inférieur ou égal à 305, et supérieur ou égal à 289 pour l'égalité.
----- Solutions u(1) > u(0): {89,98,179,188,197,269,278,287}
----- Solutions u(1) = u(0): {296}
Pour S(U(n)) = 18, on a u(n) inférieur ou égal à 341, et supérieur ou égal à 324 pour l'égalité.
----- Solutions u(1) > u(0): {99,189,198,279,288,297}
----- Solutions u(1) = u(0): --
Pour S(U(n)) = 19, on a u(n) inférieur ou égal à 379, et supérieur ou égal à 361 pour l'égalité.
----- Solutions u(1) > u(0): {199,289,298}
----- Solutions u(1) = u(0): {379}
Pour S(U(n)) = 20, on a u(n) inférieur ou égal à 419, et supérieur ou égal à 400 pour l'égalité.
----- Solutions u(1) > u(0): {299,389,398}
----- Solutions u(1) = u(0): --
Pour S(U(n)) = 21, on a u(n) inférieur ou égal à 461, et supérieur ou égal à 441 pour l'égalité.
----- Solutions u(1) > u(0): {399}
----- Solutions u(1) = u(0): --
Pour S(U(n)) = 22, on a u(n) inférieur ou égal à 505, et supérieur ou égal à 484 pour l'égalité.
----- Solutions u(1) > u(0): --
----- Solutions u(1) = u(0): {499}

Au delà, c'est inutile, il n'y a plus de solutions.
On peut pousser un peu par acquis de conscience (s=36 par exemple), et ensuite montrer que u(n) a au moins 5 chiffres (disons un nombre noté k de chiffres), donc s <= 9k et u/s >= 10^k/9k, donc plus aucune solution

nodgim · #7

C'est correct, Scarta, bravo !

Et à la main, s'il vous plait !

J'ai fait moins de calculs que toi, je n'ai pas détaillé autant, pourtant c'est la même idée.

nodgim · #8

Le temps est passé, une ou deux remarques pour la méthode manuelle.

Pour la question 2, il s'agit de trouver "a" tel que la somme des chiffres est comprise dans l'intervalle [ a² ; a(a+1) [. C'est tout de même assez vite vu, car on se rend qu'à partir de a = 27, s(a) est vraiment trop petit, et ça ne s'arrange pas quand a croît. s(1999) = 28 mais V1999 = au moins 40 et pour s = 40, il faudrait aller chercher 49999 dont le s est bien trop grand.

Pour la question 3, c'est un peu différent. Il faut chercher dans un intervalle [ a² ; (a+1)² [ le PLUS GRAND nombre pour lequel s est plus grand que a.
C'est assez vite aussi.

J'avais idée de demander si 2017 avait un antécédent, mais c'est assez poussif à la main....

Merci pour votre participation.

scarta · #9

Assez poussif à la main, surtout quand il n'y en a pas

nodgim · #10

Non, il n'y a pas de solution de 2017.

Pour savoir si un nombre A a un antécédent, on peut utiliser la formule (A-n)n/(n-1), avec n qui varie de 1 à un max, ce max dépend de la somme des chiffres max au dessus de A.

[(A-n)n/(n-1)] est solution si la somme de ses chiffres vaut n.

scarta · #11

Plus bourrin:

Code:

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

int main (int argc, char** argv)
{
  unsigned int target = 2017, current = 1, sum = 1, mod = 9, copy;
  while(current >0)
  {
    current++; mod--;
    if(mod) sum++;
    else
    {
      mod = 10; copy = current/10; sum = 0;
      while(copy)
      {
        sum += copy % 10;
        copy /= 10;
      }
    }
    if(current + sum - current/sum == target) break;
  }
  printf("%d", current);
}

Jusqu'à 4 milliards (2^32-1) exactement en moins d'une minute

nodgim · #12

Pas mal....
Juste pour le fun, j'ai trouvé ce nombre 1097 qui a 4 antécédents :
1224, 1207, 1174 et 1166.

nodgim · #13

Evidemment, le champion pour son nombre d'antécédents est 1, qui en a une infinité.
Sinon 2476 en a 5 : 2711, 2651, 2593, 2585 et 2577.

scarta · #14

Essaye 55.585.636

nodgim · #15

Chouette, 11 antécédents !

scarta · #16

J'ai optimisé mon code, il peut louper des solutions, mais bon sur les int32 j'ai pu trouver 2144810431, pas mieux

Antécédents
2186865484
2187706587
2189493931
2191436696
2192472838
2195877301
2197122837
2204388460
2206090692
2211835722
2221410773
2230602821

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 13-09-2017 10:52:40

Suite autoalimenttée

#0 Pub

#2 - 13-09-2017 18:21:37

Suite atoalimentée

#3 - 13-09-2017 19:16:21

Suite utoalimentée

Code:

Code:

Code:

#4 - 13-09-2017 19:57:16

suite auyoalimentée

#5 - 13-09-2017 20:02:26

Suite autoalimmentée

#6 - 15-09-2017 11:44:10

Suite aautoalimentée

#7 - 15-09-2017 18:25:32

Suite auoalimentée

#8 - 16-09-2017 12:15:49

suite autoalilentée

#9 - 18-09-2017 11:08:41

Suite autoalimente

#10 - 18-09-2017 11:45:54

Suite autoalimeentée

#11 - 18-09-2017 14:51:46

suite autoalimenyée

Code:

#12 - 18-09-2017 18:53:46

Suite autoalimenttée

#13 - 19-09-2017 06:25:17

suite autoalimentéz

#14 - 19-09-2017 12:26:29

Suite autoaalimentée

#15 - 19-09-2017 15:01:04

Suite autoalimenéte

#16 - 03-10-2017 11:16:21

suite autoalilentée

Réponse rapide

Sujets similaires

Pied de page des forums