Добірка наукової літератури з теми "Nombres de Fibonacci"

Every positive integer can be written as a sum of Fibonacci numbers; it can also be written as a (finite) sum of (positive and negative) powers of the golden mean φ. We show that there exists a letter-to-letter finite two-tape automaton that maps the Fibonacci representation of any positive integer onto its φ-expansion, provided the latter is folded around the radix point. As a corollary, the set of φ-expansions of the positive integers is a linear context-free language. These results are actually proved in the more general case of quadratic Pisot units. Résumé: Tout nombre entier positif peut s'écrire comme une somme de nombres de Fibonacci; tout entier peut également s'écrire comme une somme (finie) de puissances (positives et négatives) du "nombre d'or" φ. Nous montrons qu'il existe un automate à deux bandes, fini et lettre-à-lettre, qui envoie la représentation d'un entier en base de Fibonacci sur sa représentation dans la base φ modulo le fait qu'on a replié cette dernière autour du point décimal. On en déduit que l'ensemble des représentations des entiers en base φ est un langage context-free linéaire. Tous ces résultats sont en fait établis dans le cas général où la base considérée est un nombre de Pisot quadratique unitaire.

AbstractLet Bn(x) denote the number of 1’s occurring in the binary expansion of an irrational number x>0. A difficult problem is to provide nontrivial lower bounds for Bn(x) for interesting numbers such as $\sqrt {2}$, e or π: their conjectural simple normality in base 2 is equivalent to Bn(x)∼n/2. In this article, amongst other things, we prove inequalities relating Bn(x+y), Bn(xy) and Bn(1/x) to Bn(x) and Bn(y) for any irrational numbers x,y>0, which we prove to be sharp up to a multiplicative constant. As a by-product, we provide an answer to a question raised by Bailey et al. (D. H. Bailey, J. M. Borwein, R. E. Crandall and C. Pomerance, ‘On the binary expansions of algebraic numbers’, J. Théor. Nombres Bordeaux16(3) (2004), 487–518) concerning the binary digits of the square of a series related to the Fibonacci sequence. We also obtain a slight refinement of the main theorem of the same article, which provides a nontrivial lower bound for Bn(α) for any real irrational algebraic number. We conclude the article with effective or conjectural lower bounds for Bn(x) when x is a transcendental number.

International audience We consider a large family of equivalence relations on permutations in $S_n$ that generalise those discovered by Knuth in his study of the Robinson-Schensted correspondence. In our most general setting, two permutations are equivalent if one can be obtained from the other by a sequence of pattern-replacing moves of prescribed form; however, we limit our focus to patterns where two elements are transposed, conditional upon the presence of a third element of suitable value and location. For some relations of this type, we compute the number of equivalence classes, determine how many $n$-permutations are equivalent to the identity permutation, or characterise this equivalence class. Although our results include familiar integer sequences (e.g., Catalan, Fibonacci, and Tribonacci numbers) and special classes of permutations (layered, connected, and $123$-avoiding), some of the sequences that arise appear to be new. Nous considérons une famille de relations d’équivalence sur l'ensemble $S_n$ des permutations, qui généralisent les relations de Knuth liées à la correspondance Robinson-Schensted. Dans notre contexte général, deux permutations sont considérées comme équivalentes si l'une peut être obtenue de l'autre auprès d'une séquence de remplacements d'un motif par un autre selon des règles précisées. Désormais, nous ne considérons dans l’œuvre actuelle que les motifs qui correspondent à la transposition de deux éléments, conditionné sur la présence d'un élément de valeur et de position approprié. Pour plusieurs exemples de ce problème, nous énumérons les classes d'équivalence, nous déterminons combien de permutations sur $n$ éléments sont équivalentes à l'identité, ou nous précisons la forme des éléments dans cette dernière classe. Bien que nos résultats retrouvent des séquences des entiers très bien connues (nombres de Catalan, de Fibonacci, de Tribonacci...) ainsi que des classes de permutations déjà étudiées (en couches, connexes, sans motif $123$), nous trouvons également des séquences qui paraissent être nouvelles.

International audience A convex polyomino is $k$-$\textit{convex}$ if every pair of its cells can be connected by means of a $\textit{monotone path}$, internal to the polyomino, and having at most $k$ changes of direction. The number $k$-convex polyominoes of given semi-perimeter has been determined only for small values of $k$, precisely $k=1,2$. In this paper we consider the problem of enumerating a subclass of $k$-convex polyominoes, precisely the $k$-$\textit{convex parallelogram polyominoes}$ (briefly, $k$-$\textit{parallelogram polyominoes}$). For each $k \geq 1$, we give a recursive decomposition for the class of $k$-parallelogram polyominoes, and then use it to obtain the generating function of the class, which turns out to be a rational function. We are then able to express such a generating function in terms of the $\textit{Fibonacci polynomials}$. Un polyomino convexe est dit $k$-$\textit{convexe}$ lorsqu’on peut relier tout couple de cellules par un chemin monotone ayant au plus $k$ changements de direction. Le nombre de polyominos $k$-convexes n’est connu que pour les petites valeurs de $k = 1,2$. Dans cet article, nous énumérons la sous-classe des polyominos $k$-convexes qui sont également parallélogramme, que nous appelons $k$-$\textit{parallélogrammes}$. Nous donnons une décomposition récursive de la classe des polyominos $k$-parallélogrammes pour chaque $k$, et en déduisons la fonction génératrice, rationnelle, selon le demi-périmètre. Nous donnons enfin une expression de cette fonction génératrice en termes des $\textit{polynômes de Fibonacci}$.

Nous donnons une construction générale d'espaces probabilisés sur [0,1], avec une mesure notée µ. Puis nous définirons cette mesure µ dans le cadre des groupes profinis, en particulier dans le cas où ces groupes profinis proviennent des groupes de Galois, définis sur des tours d'extensions galoisiennes de corps de nombres. Nous ferons apparaître ces tours d'extensions de corps en étudiant des propriétés liées à la divisibilité par des nombres premiers de termes de certaines suites récurrentes linéaires intégrales. Par exemple, nous allons démontrer les conjectures de Paul S. Bruckman et Peter G. Anderson, attachées à la notion de Z-densité définie pour la suite de Fibonacci. Puis, nous calculerons la densité des diviseurs premiers maximaux d'une famille de suites récurrentes linéaires intégrales d'ordre 3
We give a general construction of probability measures on [0, 1] linked with representations of real numbers in a variable basis and with some so-called density function. This general constructions is shown to naturally associate a probability space to a profinite group and, in particular, to define a probability measure on the Galois group of an infinite Galois extension of a number field. Our probabilistic formalism is then applied on two distinct problems. First, we solve conjectures of Paul Bruckman and Peter Anderson on the rank of an integer in the Fibonacci sequence. Secondly, we compute the density of maximal prime divisors for an infinite family of third order integral linear recurring sequences

Cette thèse porte sur les minorations des plus grands diviseurs premiers de suites récurrentes linéaires. Tout d’abord, nous obtenons une version uniforme et explicite du résultat séminal de Stewart sur les diviseurs premiers des suites de Lucas. Nous montrons que les constantes du théorème de Stewart ne dépendent que du corps quadratique correspondant à la suite de Lucas, mais pas d’autres paramètres. Nous étudions ensuite les diviseurs premiers des ordres de courbes elliptiques sur des corps finis. En fixant une courbe elliptique sur un corps fini Fq avec q puissance d’un nombre premier, la suite #E(Fqn) s’avère être une suite récurrente linéaire d’ordre 4. Soit P(x) le plus grand nombre premier divisant x. Une minoration de P(#E(Fqn)) est donnée en utilisant l’argument de Stewart et quelques discussions plus délicates. Ensuite, motivés par nos deux projets précédents, nous pouvons montrer que lorsque γ est un nombre algébrique de degré 2 et non une racine d’unité, il existe un idéal premier p de Q(γ) vérifiant νp(γn − 1) ≥ 1, tel que le nombre premier rationnel p sous-jacent à p croît plus rapidement que n. Enfin, nous considérons une application de la méthode de Stewart aux nombres de Fibonacci Fn. Nous obtenons des bornes relativement plus nettes pour P(Fn). Tous les sujets ci-dessus s’appuient essentiellement sur l’estimation de Yu pour des formes linéaires de logarithmique p-adiques
This thesis is about lower bounds for the biggest prime divisors of linear recurrent sequences. First, we obtain a uniform and explicit version of Stewart’s seminal result about prime divisors of Lucas sequences. We show that constants in Stewart’s theorem depend only on the quadratic field corresponding to a Lucas sequence. Then we study the prime divisors of orders of elliptic curves over finite fields. Fixing an elliptic curve over Fq with q power of a prime number, the sequence #E(Fqn) happens to be a linear recurrent sequence of order 4. Let P(x) be the biggest prime dividing x. A lower bound of P(#E(Fqn)) is given by using Stewart’s argument and some more delicate discussions. Next, motivated by our previous two projects, we can show that when γ is an algebraic number of degree 2 and not a root of unity, there exists a prime ideal p of Q(γ) satisfying νp(γn − 1) ≥ 1, such that the rational prime p underlying p grows quicker than n. Finally, we consider a numerical application of Stewart’s method to Fibonacci numbers Fn. Relatively sharp bounds for P(Fn) are obtained. All of the above work relies heavily on Yu’s estimate for p-adic logarithmic forms