Créez une fonction, une expression ou un programme qui effectue les opérations suivantes:
- Prenez les facteurs premiers de n'importe quel nombre et additionnez-les. Par exemple, les facteurs premiers de 28 sont 2 2 7, sommés à 11.
- Multipliez le résultat par le nombre de facteurs premiers pour le nombre donné. Par exemple, 28 a 3 facteurs premiers qui totalisent 11. 11 * 3 est 33.
- Répétez le processus récursivement, en stockant la liste résultante (qui commence par le numéro d'origine), jusqu'à ce que vous atteigniez un numéro qui est déjà inclus dans la liste. Arrêtez sans ajouter ce numéro final, afin que la liste ne contienne aucun doublon. La progression pour 28 est de 28 33, car 33 se traduit à nouveau par 28.
- Comptez les éléments dans la liste résultante. Dans le cas de 28, la réponse est 2.
Voici les résultats pour 0<n<=10
, afin que vous puissiez vérifier votre algorithme.
2 1 1 10 1 11 1 9 5 10
(Comme l'a souligné balpha, la réponse pour higley(1)
est 2, dans la liste 1 0. J'en avais à l'origine 1, en raison d'un bug dans mon algorithme original écrit en J.)
Étant donné que je suis un SOB prétentieux et que je ne l'ai pas trouvé sur OEIS , appelons cela la "séquence Higley", au moins pour la durée de cette ronde de golf de code. En prime, trouvez les deux premiers n
ayant le plus bas higley(n)
où n
n'est pas premier et n>1
. (Je pense qu'il n'y en a que deux, mais je ne peux pas le prouver.)
C'est le golf à code standard, donc comme d'habitude, le moins de frappes gagnent, mais je vous demande de bien vouloir voter pour des réponses intelligentes dans d'autres langues, même si elles sont verbeuses.
highley(1) == 1
? On n'a pas de facteurs premiers, donc la liste résultante en 4) est[1, 0]
,highley(1) == 2
comme je le vois.Réponses:
J,
4745Il est possible que ce soit beaucoup plus court sans utilisation
^:_
, mais mon cerveau est déjà suffisamment frit.Edit: (47-> 45) Double coupon jour.
Usage:
la source
#@((~.@,((+/*#)@:q:)@{:)^:_)`2:@.(=&1)
qui est de 38 caractères.{
,{.
, et{:
toutes les choses moyennes différentes, mais{-
(par exemple) est sans aucun doute une séquence de deux choses,{
et-
.Golfscript,
68 67 6261 caractèresC'est une expression: elle prend
n
la pile et laisse le résultat sur la pile. Pour le transformer en un programme qui prendn
de stdin et imprime le résultat sur stdout, remplacez le début[
par~
Le cœur de celui-ci est
[.2@{1$1$%{)}{\1$/1$}if}*;;]
(28 caractères) qui prend le premier numéro de la pile et (par un algorithme incroyablement inefficace) génère une liste de ses facteurs premiers. Équivalent de pseudocode de style C:Le
0+
juste avant{+}*
est de gérer le cas spécialn==1
, car Golfscript n'aime pas plier une opération binaire sur la liste vide.L'un des points fixes non premiers est 27; J'ai trouvé cela sans utiliser le programme en considérant le mappage (p a
->
a 2 p), qui est un point fixe si a == p (a-1) / 2 , et en essayant petita
. (a==1
donne la fixpointedness des nombres premiers).La recherche avec le programme fait apparaître un deuxième point fixe: 30 = (2 + 3 + 5) * 3
Annexe: preuve qu'il n'y a que deux points fixes non principaux
Notation:
sopfr(x)
est la somme des facteurs premiers dex
, avec répétition (A001414).Omega(x)
est le nombre de facteurs premiers dex
(A001222). Ainsi, la fonction successeur de Higley esth(x) = sopfr(x) Omega(x)
Supposons que nous ayons un point fixe
N = h(N)
qui est un produit den=Omega(N)
nombres premiers.N = p_0 ... p_{n-1} = h(N) = n (p_0 + ... + p_{n-1})
Théorie des nombres de base:
n
divise enp_0 ... p_{n-1}
, doncw=Omega(n)
ces nombres premiers sont les facteurs premiers den
. Wlog, nous les considérerons comme les derniersw
. Nous pouvons donc diviser les deux côtésn
et obtenirp_0 ... p_{n-w-1} = p_0 + ... + p_{n-1}
ou
p_0 ... p_{n-w-1} = p_0 + ... + p_{n-w-1} + sopfr(n)
Étant donné que tous les nombres premiers
p_0
àp_{n-w-1}
sont supérieurs à 1, l'augmentation de l'un d'eux augmente le LHS plus que le RHS. Donc pour une donnéen
, on peut énumérer toutes les solutions candidates.En particulier, il ne peut y avoir de solutions si le LHS est supérieur au RHS en fixant tous les nombres premiers "libres" à 2. C'est-à-dire qu'il n'y a pas de solutions si
2^{n-w} > 2 (n-w) + sopfr(n)
Puisque
sopfr(n) <= n
(avec égalité uniquement pour n = 4 ou n premier), nous pouvons affirmer plus faiblement qu'il n'y a pas de points fixes si2^{n-w} > 3 n - 2 w
Tenir
w
fixe, nous pouvons sélectionner différentes valeurs den
satisfactionw=Omega(n)
. Le plus petitn
est2^w
. Notez que si2^{n-w}
est au moins 3 (c'est-à-dire sin-w>1
, ce qui est vrai sin>2
), alors augmentern
tout en maintenantw
constant augmentera le LHS plus que le RHS. Notez également que pourw>2
et en prenant le plus petit possiblen
l'inégalité est satisfaite, et qu'il n'y a pas de points fixes.Cela nous laisse avec trois cas:
w = 0
etn = 1
;w = 1
etn
est premier; ouw = 2
etn
est semi-prime.Affaire
w = 0
.n = 1
, toutN
comme tout premier.Affaire
w = 1
. Sin = 2
alorsN = 2p
et nous avons besoinp = p + 2
, ce qui n'a pas de solutions. Sin = 3
alors nous avonspq = p + q + 3
et deux solutions,(p=2, q=5)
et(p=3, q=3)
. Sin = 5
alors2^4 > 3 * 5 - 2 * 1
, donc il n'y a pas d' autres solutions avecw = 1
.Affaire
w = 2
. Sin = 4
alorsN = 4pq
et nous avons besoinpq = p + q + 4
. Cela a une solution entièrep=2, q=6
, mais pas de solutions principales. Sin = 6
alors2^4 > 3 * 6 - 2 * 2
, donc il n'y a pas d' autres solutions avecw = 2
.Tous les cas sont épuisés, donc les seuls points fixes non principaux sont 27 et 30.
la source
n
avant qu'elle ne soit comptée, y a-t-il un nombre non premiern
après 49 pour lequel ladite séquence ne se termine pas en 28?n
dont les borneshigley(n)
ci-dessus. (Cela permettrait de simplifier considérablement la boucle - il suffit d'itérer lesf(n)
temps, puis de supprimer les doublons).Ruby, 92 caractères
Cette solution suppose que higley (1) est en fait 2, pas 1 (voir le commentaire de balpha ci-dessus):
la source
Octave - 109 caractères
la source
MATL , 19 octets
Essayez-le en ligne!
la source