Un problème pour l'an neuf
dans Arithmétique
Soit $f$ de $\N^*$ vers $\Z$ telle que : 1) $\forall n \in \N^*$ et $\forall m \in \N^*$ $f(nm)=f(n)+f(m)$
et 2) $ \forall p $ premier $f(1)+f(2)+\cdots +f(p)=p$.
Calculez $f(2018)$.
et 2) $ \forall p $ premier $f(1)+f(2)+\cdots +f(p)=p$.
Calculez $f(2018)$.
Réponses
-
Une méthode de type "force brute" aboutit (merci le tableur) et fait apparaître un raisonnement sous-jacent simple et efficace. Joli problème.
-
En effet, c'est un problème pour Python, que malheureusement je ne maîtrise pas. Très belle trouvaille.
-
Bonne nuit,
$f(2018)=-10$ ?
Cordialement,
Rescassol -
Je trouve la même valeur.
écrit pour GP PARI:H(m)={ local(n,k,D); T=vector(m); for(n=2,m,if(isprime(n)==1,T[n]=n-sum(k=1,n-1,T[k]),D=factor(n);T[n]=T[D[1,1]]+T[n/D[1,1]])); return(T[m]); }
Le code est tout pourri et sans subtilité mais il fonctionne semble-t-il.
PS:
Merci Cidrolin pour ce problème. -
Je confirme. Programme en python :
N=2019 F=[0]*N F[2]=2 S=2 for n in xrange(3,N): d=2 while (((d*d)<=n) and ((n%d)>0)): d+=1 if ((n%d)==0): F[n]=F[d]+F[n/d] else: F[n]=(n-S) S+=F[n] print(F[2018])
-
Bonjour,
FdP, voilà au moins aussi pourri:def cidrolin(n): if Tbool[n]: return Tval[n] b,m=Premier(n) Tbool[n]=True if b: Tval[n]=n-sum(cidrolin(k) for k in range(2,n)) else: Tval[n]=cidrolin(m)+cidrolin(n//m) return Tval[n] N=2019 Tval=[0]*N Tbool=[False]*N Tval[1]=0 Tbool[1]=True Tval[2]=2 Tbool[2]=True print(cidrolin(2018))
Edit: j'avais oublié de préciser ceci (écrit un autre jour):def Premier(n): if n == 1: return False, 1 if not n % 2: return False, 2 limite = int(sqrt(n)) + 1 for k in range(3,limite,2): if not n % k: return False, k return True, 1
Cordialement,
Rescassol -
Bonjour,
Et un petit graphique:
Cordialement,
Rescassol -
J'avais trop honte du code que j'ai donné ci-dessus.
Voici une version un peu plus optimisée:F(m)={ local(n,k,D,S); T=vector(m); S=0; for(n=2,m,if(isprime(n),T[n]=n-S;,D=divisors(n);T[n]=T[D[2]]+T[n/D[2]]);S+=T[n]); return(T[m]); }
Explications pour les non informaticiens.
On calcule toutes les valeurs de $F$ de $2$ à $m$.
On sait que $F(1)=0$ puisque $F(n\times 1)=F(n)+F(1)$.
Une fois qu'on a calculé toutes les valeurs de $F$ de $2$ à $n-1$.
On se retrouve devant l'alternative.
Ou bien, $n$ est premier et on a alors une formule qui permet de calculer $F(n)$:
$\displaystyle F(n)=n-\sum_{k=1}^{n-1}F(k)$
Les valeurs de $k$ sont plus petites que $n$ donc les $F(k)$ ont déjà été calculées.
Ou bien, $n$ n'est pas premier et dans ce cas-là il a au moins un diviseur $d$ qui n'est pas $1$ et qui n'est pas $n$.
(le deuxième plus petit diviseur: D[2] dans mon programme) et on a: $n=dd'$ et donc $F(n)=F(d)+F(d')$
$d$ et $d'$ sont plus petits que $n$ on a donc déjà calculé $F(d)$ et $F(d')$.
Toutes les valeurs de $F$ sont sauvegardées dans le tableau $T$ de mon programme qui a exactement $m$ entrées.
(par défaut, à la création toutes les entrées sont mises à $0$)
A chaque fois qu'on obtient une nouvelle valeur de F, on l'ajoute à la variable $S$. $S$ est donc égale à la somme des $F(k)$ pour $k$ variant de $1$ à la dernière valeur traitée. Cela évite de recalculer cette somme à chaque fois qu'on rencontre un nombre premier. -
Il y a un rapport avec le problème proposé par Cidrolin il y a un mois: Nouvelles factorisations.
En effet si $p$ est premier on a $f(p!)=p$.
Par suite si $n=\prod p_k^{(a_k)}$ (avec les notations de Cidrolin) on a $f(n)=\sum p_ka_k$.
Par exemple, $2018=1009^{(1)}997^{(-1)}503^{(-1)}491^{(1)}83^{(1)}79^{(-1)}71^{(1)}67^{(-2)}61^{(1)}59^{(-1)}47^{(1)}37^{(-1)}31^{(3)}23^{(-3)}19^{(2)}13^{(-1)}11^{(4)}7^{(-3)}5^{(-8)}3^{(-9)}2^{(16)}$ donne bien $f(2018)=-10$. -
Merci à tous !
Voici quelques explications : nul n'ignore la suite A001414 de l'oeis.
Notons $g(n)$ le terme de rang $n$ de cette suite, $g$ est complètement additive (prop 1 de $f$) et vérifie: $p$ premier $=>$ $\quad g(p)=p$.
La fonction $f$ de ce fil correspond à la même idée, mais pour la "factorisation" de http://www.les-mathematiques.net/phorum/read.php?5,1552962 .
Précisons, si $n=(p_1!)^{a_1}(p_2!)^{a_2}\cdots (p_k!)^{a_k}$ alors $f(n)=p_1*a_1+\cdots+p_k*a_k$.
par exemple
$f(2018)=1009*1 -997*1 -503*1 +491*1+ 83*1 -79*1 +71*1 -67*2 +61*1 -59*1$
$+47*1 -37*1 +31*3 -23*3 +19*2 -13*1 +11*4 -7*3 -5*8 -3*9 +2*16 =-10$
Amicalement
Edit : grillé par Jandri :-D -
Merci pour ces détails mais est-ce que cela améliore la "vitesse" de calcul de $F(n)$ pour $n$ un nombre quelconque?
(je suis un peu déçu, à priori, je m'attendais à un "big trick" qui ridiculise mon programme au dernier degré) -
Plus précisément, il semblerait que $\displaystyle \sum_{k=1}^n f(k) = n + \mathcal{O}(\sqrt{n})$.
-
Pour enfoncer des portes déjà ouvertes.
On peut prolonger la fonction $F$ à l'ensemble $\mathbb{Q}_{*}^{+}$ en entier.
$F\left(\frac{a}{b}\right)=F(a)-F(b)$ -
Si $p$ premier possède un jumeau $p+2$, alors $f(1)+f(2)+ \dots +f(p)+f(p+1)+f(p+2)=p+2$,
qui donne $f(p+1)+f(p+2)=2$. La réciproque est fausse $f(20)+f(21)=2$. -
Existe-il une infinité de $n$ tels que $f(n)+f(n+1)=2$?
-
Il y a exactement 76 valeurs de $n$ inférieures à $1000$ qui sont telles que $F(n)+F(n+1)=2$
PS:
et exactement $511$ valeurs qui sont inférieures à $10000$ -
Pour comparaison, combien de petits jumeaux dans les mêmes intervalles?
-
D'après wiki il y a 35 paires de petits jumeaux infèrieurs à 1000.
-
Et d'après http://villemin.gerard.free.fr/Wwwgvmm/Premier/jumeaux.htm il y en a 205 infèrieurs à 10000. D'où conjecture: il y a asymptotiquement deux fois plus de valeurs de $n$ telles que $f(n+1)+f(n)=2$ que de couples de petits jumeaux.
-
(À supposer qu'il existe une infinité de petits jumeaux, sinon le comportement asymptotique n'est pas très asymptotique).
-
Remarquons que $f(p+1)+f(p+2)=2$ peut se réécrire $f(p+1)+f(p+2)=f(2)$, ou encore $f(\frac{(p+2)(p+1}{2})=0$.
Il conviendrait donc de chercher les $n$ premiers tels que $f(t_n)=0$, ici $t_n=n(n-1)/2$.
Il y a une infinité de nombres premiers et aussi une infinité de nombres $m$ vérifiant $f(m)=0$ donc . . . -
Il y a $39$ nombres premiers inférieurs à $1000$ et vérifiant $f(n(n-1)/2)=0$ ce sont :
[5, 7, 13, 19, 23, 31, 43, 61, 73, 103, 109, 139, 151, 179, 181, 193, 199, 229, 241, 271, 283, 313, 349, 401, 421, 433, 463, 523, 571, 601, 619, 643, 661, 811, 823, 827, 829, 859, 883]
Dans cette liste, il y a $4$ intrus ($n-2$ n'est pas premier) : $23,179,401,827$.
On retrouve les $35$ nombres annoncés plus haut. -
Cidrolin a écrit:
Il y a une infinité de nombres premiers et aussi une infinité de nombres m vérifiant f(m)=0 donc . . .
Donc? -
Donc on ne peut rien dire. Évitons un déplacement vers Shtam.
-
Remarquons que:
$23-2=3 \times 7$
$179-2 = 3 \times 59$
$401-2=3 \times 7 \times 19$
$827-2=3 \times 5^2 \times 11$. -
Shah d'Ock, Cidrolin,
Je me sens obligé d'alerter un modérateur. -
Shah d'Ock:
et? -
Ceci laisse envisager que les intrus soient tous congrus à 2 modulo 3.
-
Autrement dit, on peut conjecturer que si $n>3$ n'est pas un multiple de $3$, si $n+2$ est premier et si $f(\frac{(n+1)(n+2)}2)=0$ alors $n$ est un petit jumeau.
-
Je vais poursuivre les calculs.
-
Trouver un entier dont l'écriture décimale se termine par $2018$, tel que si on déplace $2018$ devant le nombre, il double.
On part de $a_1a_2 \cdots a_n 2018$, on arrive à $2018a_1a_2 \cdots a_n $. -
Bonsoir,
Pour le plus petit:100905045252262613130656532826641332066603330166508325416270813540677033851692584629231461573078653932696634831741587079353967698384919245962298114905745287264363218160908045402270113505675283764188209410470523526176308815440772038601930096504825241262063103155157757887894394719735986799339966998349917495874793739686984349217460873043652182609130456522826141307065353267663383169158457922896144807240362018
Cordialement,
Rescassol -
Et le deuxième?
-
Bonsoir,
Pas de problème, voilà le deuxième:100905045252262613130656532826641332066603330166508325416270813540677033851692584629231461573078653932696634831741587079353967698384919245962298114905745287264363218160908045402270113505675283764188209410470523526176308815440772038601930096504825241262063103155157757887894394719735986799339966998349917495874793739686984349217460873043652182609130456522826141307065353267663383169158457922896144807240362018100905045252262613130656532826641332066603330166508325416270813540677033851692584629231461573078653932696634831741587079353967698384919245962298114905745287264363218160908045402270113505675283764188209410470523526176308815440772038601930096504825241262063103155157757887894394719735986799339966998349917495874793739686984349217460873043652182609130456522826141307065353267663383169158457922896144807240362018
Cordialement,
Rescassol -
Est-ce la concaténation du premier avec lui-même?
-
Oui, j'avais mal lu.
-
C'est pas l'an neuf, c'est l'an dix-huit.
-
J'essaie de faire du Cidrolin mais je n'ai pas le niveau ;-).
-
Pour quelles dates la deuxième solution du problème associé est-elle la concaténation de la première solution avec elle-même?
-
Merci pour vos réponses.
Je considère le rationnel $x=0,a_1a_2 \cdots a_n 2018a_1a_2 \cdots a_n 2018a_1a_2 \cdots a_n 2018\cdots$.
On doit avoir $\dfrac{x}{10\,000} +\dfrac{2\,018}{10\,000}=2x$.
On trouve $x=\dfrac{2\,018}{19\,999}$. Le nombre cherché correspond à la période (repeating decimal), avec wolframalpha : -
Joli!
-
Ça ne marcherait pas avec 5018...
-
Si, il faut trouver la période de 5018/19999.
-
C'est :
-
Mais $0,5018a_1 \dots a_n 5018 a_1 \dots a_n \dots$ n'est plus le double de $0,a_1 \dots a_n 5018 a_1 \dots a_n \dots$, ou me trompé-je?
-
Autant pour moi, je me suis embrouillé tout seul.
-
Plutôt que $5018$, mieux vaut demander pour $2857$, dans $840$ ans.
Le nombre $142857$ a pour double $285714$. -
Joli. J'espère vivre assez vieux pour voir ça.
-
Un troisième problème :
On classe dans l'ordre croissant le nombres $n \pi^m$, avec $n \geq 1$ et $m \geq 1$.
On trouve :$\pi ; 2\pi; 3\pi; \pi^2;4\pi. \dots$
Quel est le $2018$ème ? Quel est le rang de $n \pi^m$ ?
Amicalement
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres