Une suite récurrente

Maxtimax · May 2019

Bonjour,
J'ai vu passer une conjecture qui m'a mené à une autre question liée, qui m'a l'air tout autant intéressante que la conjecture; et ma première idée bête que j'ai eue pour y répondre a l'air de marcher mais je ne sais pas le prouver. Je mets les 3 dans l'ordre, ma question concerne uniquement la dernière (je ne m'attends pas à ce que vous sachiez prouver la conjecture)

1) (la conjecture) Existe-t-il une permutation $\sigma$ de $\{1,...,n\}$ telle que pour tout $i<n, \sigma (i)+\sigma (i+1)$ soit un carré ? La conjecture est que oui, si $n>24$.
2) (la question liée) Quid d'une permutation de $\mathbb{N}$ ?
3) (ma vraie question) Si je définis $u_0= 0$ et $u_{k+1} = $ le plus petit entier $j$ n'appartenant pas à $\{u_0,...,u_k\}$ tel que $u_k+j$ est un carré, a-t-on que $u$ est une permutation ?
Evidemment, $u$ est automatiquement injective par construction, donc la question c'est : est-elle surjective, i.e. atteint-on tout le monde ?

Si on fait des tous petits exemples on a l'impression que non, mais si on va plus loin que $5$ ou $6$ on se rend compte que c'est plausible. J'ai fait des tests sur CamL (je m'y suis remis récemment rapidement, ça me donne une occasion de tester mes compétences :-D ), elle est surjective au moins jusqu'à 4206 (sachant que je ne suis allé que jusqu'à 5000 en gros, donc le plus petit $n$ tel que $u_n=k$ n'est pas beaucoup plus gros que $k$, même si les premiers exemples laissent supposer le contraire) si je n'ai pas codé n'importe quoi.

Il est clair que $u_n$ tend vers l'infini (par injectivité), et on peut en déduire assez facilement que si $k$ n'est pas atteint, alors $\{n^2-k, n\in\mathbb{N}\}\cap \mathrm{im}(u)$ est fini; et donc on obtient toute une tripotée de gens pas atteints (et on peut réitérer avec ceux-là).
Je n'ai pas beaucoup plus d'idées, et je ne suis pas doué en arithmétique, donc je me suis dit que le plus intelligent serait de vous partager le problème, en espérant qu'il vous intéressera et vous inspirera ;-) (en espérant aussi qu'il n'est pas tout bêtement trivial, ce que je redoute un peu)

rosab · May 2019

Bonjour,
Tu trouveras un peu plus de termes, mais guère plus de renseignements, dans l'encyclopédie des suites : https://oeis.org/A034175

Math Coss · May 2019

Étonnant ! Voici ma piètre contribution.

#! /usr/bin/python
# -*- coding: utf-8 -*-

from math import sqrt, ceil

def dif(L):
    return [L[k]-L[k-1] for k in range(1,len(L))]

def u(N):
    L = [0]
    while len(L)<N:
        r = int(ceil(sqrt(L[-1])))
	j = r**2-L[-1]
	while j in L:
	    r+= 1
	    j = r**2-L[-1]
	L.append(j)
    return L

L = u(30000)

L.sort()
M = dif(L)

print M
print u"Trouve-t-on deux nombres égaux ? %s" % (0 in M)
print u"Plus petit nombre qui manque : %s" % (1+min([k for k in range(len(M)) if M[k]!=1]))

Maxtimax · May 2019

Sur "suggestion" de Math Coss (j'interprète ton message ;-) ) je rajoute mon code, "for completeness" comme disent les autres:

J'ai un tableau u qui contient les entrées de la suite u, je l'ai initialisé par

let u = Array.make 10000 0;;

J'ai un tableau b qui me dit qui est déjà apparu

let b = Array.make 10000 false;;

Malheureusement celui-là, mon code fait qu'il faut le réinitialiser à chaque fois que je réutilise ma fonction (et donc il faut redéfinir ma fonction à chaque fois)
ensuite une fonction de test qu'on est un carré

let isasquare n = let rec h i = if i<=n then begin if i*i == n then true else h (i+1) end else false in h 0;;

et enfin

let rec f k = match k with
|0 -> b.(0)<- true
|k -> begin f  (k-1); let rec g i = if b.(i) then g (i+1) else
                  if isasquare (i+u.(k-1)) then begin u.(k)<- i; b.(i)<- true end else g (i+1) in g 0 end;;

Maxtimax · May 2019

@rosab : l'un des commentaires est "conjectured to be a permutation of the nonnegative integers"; il est donc probable que ce soit aussi un problème ouvert (je ne sais pas dans quelle mesure c'est à jour )

Une suite récurrente

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 33