[PDF] Algorithmes pour vérifier la conjecture de Syracuse

View - Download Algorithmes pour vérifier la conjecture de Syracuse

Previous PDF

Next PDF

INFORMATIQUE THÉORIQUE ET APPLICATIONSJACQUESARSAC Informatique théorique et applications, tome 21, no1 (1987), p. 3-9

© AFCET, 1987, tous droits réservés.

L"accès aux archives de la revue " Informatique théorique et applications » im- plique l"accord avec les conditions générales d"utilisation (http://www.numdam. org/conditions). Toute utilisation commerciale ou impression systématique est constitutive d"une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright.Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ Informatique théorique et Applications/Theoretical Informaties and Applications (vo L 21
n 1 1987
p 3 9

ALGORITHME

S POU R

VÉRIFIE

R L A

CONJECTUR

E D E

SYRACUS

E pa r

Jacque

s ARSA C l

Communiqu

pa r J

BERSTE

L

Résumé

La suite de

Syracuse

de l'entier naturel n est définie par

U(n,Q)

= n. U(n, i+\)

SIpair

U(n, i) ALORS U(n, 0/ 2 SINON 3 U(n, 0 l)/2 La conjecture de

Syracuse

dit que pour tout neN, n> 1 il existe k fini tel que U(n, k) 1

Cecin'a pu être démontré. On a vérifié que la conjecture est vraie jusqu'à 240 par calculs sur ordinateur.On examine ici la complexité de ces calculs, et on montre qu'elle peut être réduite grâce auxpropriétés des suites de Syracuse.

Abstract

The

Syracuse

Séquence

ofnatural integer n n is defined as U(n t i+\) lFeven U(nJ) THEN

U(nJ)/2

ELS E (3 U {n, i)+\)/2 It has been conjectured thatfor every wef^J n> 1 there exists afinite integer k such that U(n, k) 1

.This fact has not yet been proved. The conjecture has been verified on a computer up to 240. Weconsider hère the complexity of direct algorithms to check the conjecture, and the way in whichthe complexity may be reduced through convenient properties of séquences of Syracuse.

1

INTRODUCTIO

N Dan s c e qu i suit tou s le s nombre s son t de s entier s naturels L a suit e d e

Syracus

e d e n 1 es t défini e pa r U(n, 0) = n U (n, i l S i pai r U(n, i) ALOR S U(n, i)/2 SINO N 3 U (n i) l)/2

Reç

u e n décembr e 1984
révis e n jui n 1986
C 1

Universit

Pierre-et-Marie-Curie

4 plac e

Jussieu

7500
5 Paris

Informatiqu

e théoriqu e e t

Applications/Theoretica

l

Informatie

s an d

Application

s0296-1598 87/01 3 7/S2.70/© Gauthier-Villars

4 J. ARSAC

L a conjectur e d e

Syracus

e di t qu e pou r tou t n>\ i l exist e k(n) fin i te l qu e U(n, k(ri))= 1 Cec i n' a pa s ét encor e démontré e t

Lagaria

s [1 di t c e problèm e no n traitable bie n qu e l'o n possèd e quelque s théorèmes I l demand e s'i l exist e d e bon s programme s pou r vérifie r l a conjectur e su r ordinateu r jusqu' u n entie r N auss i gran d qu e possible Dan s un e lettr e J C

Lagarias

Shir o And o [2 annonc e qu'i l l' a fai t jusqu' 2 A 40
L e programm e utilis n'ayan tquotesdbs_dbs46.pdfusesText_46

[PDF] la suite de syracuse exercice corrigé

[PDF] la suite définie

[PDF] La Suite numérique

[PDF] La supercificie de la Terre est environ de 5,1 x 10 puissance 8 km²

[PDF] La supersitition

[PDF] la superstition

[PDF] La suprématie militaire et diplmatique

[PDF] la surface (fraction)

[PDF] la surface du globe

[PDF] La surveillance la prévision et la prévention

[PDF] la survie sur l ile p 182 francaix

[PDF] la syllabation en poésie

[PDF] La symbolique chevaleresque dans l'enluminure

[PDF] la symbolique du crane dans arts plastics (peinture,sculture)

[PDF] la symetrie !!;)