Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
83 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Un problème pour l'an neuf

Envoyé par Cidrolin 
Un problème pour l'an neuf
il y a deux semaines
avatar
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)$.
Re: Un problème pour l'an neuf
il y a deux semaines
avatar
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.
Re: Un problème pour l'an neuf
il y a deux semaines
En effet, c'est un problème pour Python, que malheureusement je ne maîtrise pas. Très belle trouvaille.
Re: Un problème pour l'an neuf
il y a deux semaines
Bonne nuit,

$f(2018)=-10$ ?

Cordialement,

Rescassol
Re: Un problème pour l'an neuf
il y a deux semaines
avatar
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.

Une théorie nouvelle ne triomphe jamais. Ses détracteurs finissent par mourir.



Edité 1 fois. La dernière correction date de il y a deux semaines et a été effectuée par Fin de partie.
Re: Un problème pour l'an neuf
la semaine dernière
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])
Re: Un problème pour l'an neuf
la semaine dernière
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



Edité 1 fois. La derni&egrave;re correction date de la semaine derni&egrave;re et a &eacute;t&eacute; effectu&eacute;e par Rescassol.
Re: Un problème pour l'an neuf
la semaine dernière
Bonjour,

Et un petit graphique:


Cordialement,

Rescassol
Re: Un problème pour l'an neuf
la semaine dernière
avatar
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.

Une théorie nouvelle ne triomphe jamais. Ses détracteurs finissent par mourir.



Edité 5 fois. La derni&egrave;re correction date de la semaine derni&egrave;re et a &eacute;t&eacute; effectu&eacute;e par Fin de partie.
Re: Un problème pour l'an neuf
la semaine dernière
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$.
Re: Un problème pour l'an neuf
la semaine dernière
avatar
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 [www.les-mathematiques.net] .

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 grinning smiley



Edité 2 fois. La derni&egrave;re correction date de la semaine derni&egrave;re et a &eacute;t&eacute; effectu&eacute;e par Cidrolin.
Re: Un problème pour l'an neuf
la semaine dernière
avatar
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é)

Une théorie nouvelle ne triomphe jamais. Ses détracteurs finissent par mourir.
Re: Un problème pour l'an neuf
la semaine dernière
Le graphique de Cidrolin montre un comportement assez chaotique de $f(n)$. Les sommes partielles se comportent plus gentiment :


Re: Un problème pour l'an neuf
la semaine dernière
Plus précisément, il semblerait que $\displaystyle \sum_{k=1}^n f(k) = n + \mathcal{O}(\sqrt{n})$.
Re: Un problème pour l'an neuf
la semaine dernière
avatar
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)$

Une théorie nouvelle ne triomphe jamais. Ses détracteurs finissent par mourir.
Re: Un problème pour l'an neuf
la semaine dernière
avatar
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$.
Re: Un problème pour l'an neuf
la semaine dernière
avatar
Existe-il une infinité de $n$ tels que $f(n)+f(n+1)=2$?

--
Objectivement, je suis subjectif.
Subjectivement, je suis objectif.
Donc objectivement, je suis objectif.
Re: Un problème pour l'an neuf
la semaine dernière
avatar
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$

Une théorie nouvelle ne triomphe jamais. Ses détracteurs finissent par mourir.



Edité 1 fois. La derni&egrave;re correction date de la semaine derni&egrave;re et a &eacute;t&eacute; effectu&eacute;e par Fin de partie.
Re: Un problème pour l'an neuf
la semaine dernière
avatar
Pour comparaison, combien de petits jumeaux dans les mêmes intervalles?

--
Objectivement, je suis subjectif.
Subjectivement, je suis objectif.
Donc objectivement, je suis objectif.



Edité 1 fois. La derni&egrave;re correction date de il y a treize jours et a &eacute;t&eacute; effectu&eacute;e par Shah d'Ock.
Re: Un problème pour l'an neuf
il y a treize jours
avatar
D'après wiki il y a 35 paires de petits jumeaux infèrieurs à 1000.

--
Objectivement, je suis subjectif.
Subjectivement, je suis objectif.
Donc objectivement, je suis objectif.
Re: Un problème pour l'an neuf
il y a treize jours
avatar
Et d'après [villemin.gerard.free.fr] 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.

--
Objectivement, je suis subjectif.
Subjectivement, je suis objectif.
Donc objectivement, je suis objectif.
Re: Un problème pour l'an neuf
il y a treize jours
avatar
(À supposer qu'il existe une infinité de petits jumeaux, sinon le comportement asymptotique n'est pas très asymptotique).

--
Objectivement, je suis subjectif.
Subjectivement, je suis objectif.
Donc objectivement, je suis objectif.
Re: Un problème pour l'an neuf
il y a douze jours
avatar
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 . . .
Re: Un problème pour l'an neuf
il y a douze jours
avatar
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.
Re: Un problème pour l'an neuf
il y a douze jours
avatar
Citation
Cidrolin

Il y a une infinité de nombres premiers et aussi une infinité de nombres m vérifiant f(m)=0 donc . . .


Donc?

--
Objectivement, je suis subjectif.
Subjectivement, je suis objectif.
Donc objectivement, je suis objectif.
Re: Un problème pour l'an neuf
il y a douze jours
avatar
Donc on ne peut rien dire. Évitons un déplacement vers Shtam.
Re: Un problème pour l'an neuf
il y a douze jours
avatar
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$.

--
Objectivement, je suis subjectif.
Subjectivement, je suis objectif.
Donc objectivement, je suis objectif.
Re: Un problème pour l'an neuf
il y a douze jours
Shah d'Ock, Cidrolin,
Je me sens obligé d'alerter un modérateur.
Re: Un problème pour l'an neuf
il y a douze jours
avatar
Shah d'Ock:

et?

Une théorie nouvelle ne triomphe jamais. Ses détracteurs finissent par mourir.
Re: Un problème pour l'an neuf
il y a douze jours
avatar
Ceci laisse envisager que les intrus soient tous congrus à 2 modulo 3.

--
Objectivement, je suis subjectif.
Subjectivement, je suis objectif.
Donc objectivement, je suis objectif.
Re: Un problème pour l'an neuf
il y a douze jours
avatar
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.

--
Objectivement, je suis subjectif.
Subjectivement, je suis objectif.
Donc objectivement, je suis objectif.



Edité 2 fois. La derni&egrave;re correction date de il y a douze jours et a &eacute;t&eacute; effectu&eacute;e par Shah d'Ock.
Re: Un problème pour l'an neuf
il y a douze jours
avatar
Je vais poursuivre les calculs.



Edité 1 fois. La derni&egrave;re correction date de il y a douze jours et a &eacute;t&eacute; effectu&eacute;e par Cidrolin.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 124 430, Messages: 1 188 217, Utilisateurs: 19 591.
Notre dernier utilisateur inscrit Pierre.tbx.


Ce forum
Discussions: 4 389, Messages: 52 483.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page