Une petite précision sur la méthode croissante du fou furieux, stp: il lit 0, donc il efface 1, puis il lit 2 et efface 5, puis lit-il 6 ou retourne t-il sur le 3 non encore lu ?

On écrit les nombres en binaire, en rajoutant un 0 au départ :

Les nombres qui se terminent par 0 sont intacts
donc ceux qui se terminent par 01 sont effacés
donc ceux qui se terminent par 011 sont intacts
donc ceux qui se terminent par 0111 sont effacés, etc...

Un nombre est donc intact si et seulement si le nombre de 1 terminaux dans l'écriture binaire est pair.

Les nombres intacts sont les nombres de la forme 2x, 8x+3, 32x+15, 128x+63, 512x+255...

De 0 à 1000, le nombre de nombres intacts est donc : 501 + 125 + 31 + 8 + 2
X = 667

De 0 à 1499, le nombre de nombres intacts est donc : 750 + 188 + 47 + 12 + 3 = 1000
Y = 1499

Je me rends compte que j'ai oublié de compter 1023, qui est un nombre de la forme 2048x+1023, ce qui rajoute 1 à mon total pour 1499 et donc j'arrive à 1001 nombres intacts jusqu'à 1499. Il faut donc enlever le dernier intact de ma liste qui est 1499, la bonne réponse est Y = 1498.

Par exemple, pour trouver combien il y a de nombres de la forme 32x+15 entre 0 et 1498, je calcule :
E((1498-15)/32) = E(1483/32) = E(46,34375) = 46
x peut prendre les valeurs de 0 à 46 donc cela fait 47 nombres de la forme 32x+15.

Le nombre d'intacts de 0 à 1498 est : 750 + 187 + 47 + 12 + 3 + 1 = 1000

Remarque : pour trouver une approximation de Y, partant du fait que 1/2 + 1/8 + 1/32 + ... = 2/3, je me suis dit qu'avec 1500 nombres on ne serait pas très loin.

Les nombres rayés sont ceux dont l'écriture binaire se termine par un nombre impair de "1".

Sur [|0;(2^n)-1|], il y a ((2^n)±1)/3 nombres rayés. Cela se démontre en remarquant que les nombres rayés sur [|0;(2^n)-2|], sont en bijection avec les nombres rayés sur [|2^n;(2^(n+1))-2|] via f(x)=x+2^n, et que (2^n)-1 est rayé <=> (2^(n+1))-1 n'est pas rayé.

Ainsi, sur [|0;1023|],  il y a (1024-1)/3=341 nombres rayés donc 1024-341=683 nombres intacts. En comptant à rebours jusqu'à 1000, je dénombre encore 7 nombres rayés (1021, 1017, 1015, 1013, 1009, 1005, 1001), donc 683-23+7=667 nombres intacts, d'où X=667 (ou 666 si 1000 ne compte pas).

Ensuite, en ajoutant 1024 avec les nombres de [|0;511|], je trouve qu'il y a 683+341=1024 nombres non rayés dans [|0;1535|], et en comptant à nouveau à l'envers, j'arrive à Y=1498.

Le fou furieux préserve tous les nombres sauf ceux de la forme 2x+1 sauf ceux de la forme 2(2x+1)+1 = 4x+3 ... sauf ceux de la forme [latex]2^n(x+1)-1[/latex]



La formule des nombres intacts jusqu'à N est donc
[TeX]intacts(N) = \sum_{n=0}^{\infty} \left\lfloor \frac{N+1}{(-2)^n}\right\rfloor[/TeX]
Mais on peut faire beaucoup plus jolie. Après tout cette somme ressemble beaucoup à 2/3 de N+1, on ne fait que retirer la moitier puis ajouter la moitier de la moitier etc...

si on écrit la somme en binaire par exemple :
+111001101011
-   11100110101
+    1110011010
-      111001101
+       11100110
-          1110011
...

On voit bien chaque puissance de [latex]2^n[/latex] dans l'écriture de N+1 contribue à la somme totale comme la somme d'une suite géométrique de raison -2,
plus précisément contribue pour [latex]\frac{2^{n+1}+(-1)^n}{3}[/latex]

Finalement :
[TeX]\boxed{intacts(N) = \frac{2(N+1)+difbin1(N+1)}{3}}[/TeX]
où [latex]difbin1(N+1)[/latex] est le nombre de "1" en position pair moins le nombre de "1" en position impaire dans l'écriture binaire de N+1

Une simple application numérique avec [latex]N=1000=\overline{1111101000}^2[/latex]permet de trouver X:
[TeX]\color{blue}{X = (2*1001 + 3 - 4)/3 = 667}[/TeX]
La résolution inverse pour Y est plus subtile :
[TeX]1667 = \frac{2(Y+1)+difbin1(Y+1)}{3}[/TeX]
Le résultat est autour de 3/2*1667 ~ 2500 avec une erreur max de 10 (en regardant l'écriture binaire de 2500)

def intacts(N):
  def difbin1(x,s):
    return difbin1(x>>1,-s) + s*(x & 1) if x else 0
  return (2*(N+1) + difbin1(N+1,1))//3

for N in range(2490,2510):
  print (N, intacts(N))

Je trouve une solution unique pour Y:
[TeX]\color{blue}{Y=2499}[/TeX]
Merci pour l'énigme

Bonjour

Il me semble que le plus simple est de compter les non-rayés qui sont tous les entiers écrits pouvant se mettre sous la forme [latex](2n+1).4^p-1[/latex] . Un petit calcul simple nous donne les X qui sont inférieurs à 1000 ( je laisse ça aux as de la programmation ) . Un petit coup d’œil au dernier nombre restant de la liste nous donne une bonne estimation du nombre Y qui terminait liste initiale . On peut ajouter 3 à ce nombre pour être certain de ne rater personne et commencer à lister les valeurs non rayées inférieures à ce nombre .

J'ai sûrement raté quelque chose car je ne trouve pas ça très émoustillant

Vasimolo

J'ai terminé ma résolution de fou furieux

Je voulais simplement dire que l'ordre des nombres rayés ne dépend absolument pas du dernier nombre inscrit et que le Y cherché est un très proche voisin du dernier entier non rayé , le reste ...

J'avoue que j'ai du mal à m'intéresser à ce type de problèmes , chacun ses goûts

Je ne remets bien sûr pas en cause la qualité de tes interventions .

Vasimolo

j'ai trouvé la "mécanique" mais le comptage exact semble un peu laborieux..Est ce la piste la plus simple ou y a il mieux ?

On a à partir de chaque nombre pair une chaine où 1 nombre sur 2 nombre est détruit :

Rang               1    2     3      4   
Détruit         N    O     N      O   
Valeur        2n  4n+1      8n+3      16n+7   

Les nombres se rangent donc ainsi :

Rang    Premier terme    intervalle    Détruit ?
1       0                        2               N
2       1                       4               O
n      2^n-1             2^(n+1)     suivant parité

@ Matthieu:
Pardon, je n'avais pas lu tes messages, je ne sais pas pourquoi je les ai ratés.
Sinon, c'est correct pour le X, mais faux pour Y. Curieusement, l'erreur vient de la méthode informatique (que je n'ai pas analysée).
Donc, ta formule générale est bonne, mais il faut peut être revoir la manière de s'en servir. Perso, j'ai mis aussi un peu de temps pour mettre au point une bonne méthode manuelle...
Tu n'es pas loin !

Oui Matthieu, en relisant ta réponse, tu n'as pas cherché combien Y faisait si Y était le 1000 ème nombre intact. C'est pourtant bien ce qui était demandé dans l'énoncé, même si c'était indirect.
Sinon tu as bien compris le raisonnement, ce qui est l'essentiel.