Comprimentos de loop narcisista
Um número narcisista é um número natural que é igual à soma de seus dígitos quando cada dígito é levado à potência dos dígitos numéricos. Por exemplo \$8208 = 8^4 + 2^4 + 0^4 + 8^4\$, então é narcisista.
Vamos definir uma função \$f(x)\$como o seguinte, para um número natural \$x = d_1d_2\dots d_n\$, onde \$d_i\$é um único dígito \$0\$para \$9\$(portanto, \$x\$tem \$n\$ dígitos):
$$f(x) = \sum_{i=1}^nd_i^n$$
Neste caso, um número é narcisista se \$f(x) = x\$.
No entanto, quando aplicamos \$f(x)\$a um número repetidamente, encontramos um padrão interessante emerge. Para qualquer \$x\$, a sequência ou atinge um ponto fixo (ou seja, um número narcisista), ou entra em um loop fixo que se repete infinitamente. Por exemplo, pegue os três inteiros \$x = 104, 127, 370\$:
\$x = 104\$: Aplicação repetida de \$f(x)\$ leva à seguinte cadeia
$$104, 65, 61, 37, 58, 89, 145, 190, 730, 370, 370, ...$$
Aqui, o loop eventualmente atinge um ponto fixo, \$370\$.
\$x = 127\$: Aplicação repetida de \$f(x)\$ leva a
$$127, 352, 160, 217, 352, 160, 217, ...$$
Aqui, o triplo \$352, 160, 217\$ repete-se ad infinitum
\$x = 370\$: \$x\$aqui já é narcisista, então a cadeia será apenas um fluxo interminável de \$370\$s.
Estes exemplos documentam os dois resultados possíveis para um determinado \$x\$. Tratando um ponto fixo como um loop de comprimento \$1\$, agora chegamos à tarefa em questão:
Dado um número natural \$n > 0\$, exibe a duração do loop que surge através da aplicação repetida de \$f(n)\$.
Os três exemplos acima retornam \$1\$, \$3\$e \$1\$respectivamente. Você pode assumir que todos \$n\$eventualmente entrar em um loop, o que parece ser o caso para pelo menos todos \$n < 10^4\$. Se existe um \$n\$para o qual isso é falso, seu programa pode fazer qualquer coisa menos convocar Cthulhu .
Este é o código-golfe, então o código mais curto em bytes vence.
A grande maioria dos números retorna \$1\$. No entanto, esses dois arrays contêm todos os \$n < 1000\$ que não, junto com quais deveriam ser seus resultados:
[ 59, 95, 106, 115, 127, 136, 138, 147, 149, 151, 157, 159, 160, 163, 168, 169, 172, 174, 175, 177, 178, 179, 183, 186, 187, 189, 194, 195, 196, 197, 198, 199, 217, 228, 229, 235, 238, 244, 245, 253, 254, 255, 258, 259, 267, 268, 271, 276, 277, 279, 282, 283, 285, 286, 289, 292, 295, 297, 298, 299, 309, 316, 318, 325, 328, 335, 352, 353, 355, 357, 358, 361, 366, 367, 369, 375, 376, 381, 382, 385, 388, 389, 390, 396, 398, 405, 408, 417, 419, 424, 425, 442, 445, 447, 450, 452, 454, 456, 457, 459, 465, 466, 468, 469, 471, 474, 475, 477, 478, 479, 480, 486, 487, 488, 491, 495, 496, 497, 499, 504, 507, 508, 511, 517, 519, 523, 524, 525, 528, 529, 532, 533, 535, 537, 538, 540, 542, 544, 546, 547, 549, 552, 553, 555, 556, 558, 559, 564, 565, 567, 568, 570, 571, 573, 574, 576, 580, 582, 583, 585, 586, 589, 591, 592, 594, 595, 598, 601, 607, 609, 610, 613, 618, 619, 627, 628, 631, 636, 637, 639, 645, 646, 648, 649, 654, 655, 657, 658, 663, 664, 666, 669, 670, 672, 673, 675, 678, 679, 681, 682, 684, 685, 687, 689, 690, 691, 693, 694, 696, 697, 698, 699, 705, 706, 708, 712, 714, 715, 717, 718, 719, 721, 726, 727, 729, 735, 736, 741, 744, 745, 747, 748, 749, 750, 751, 753, 754, 756, 760, 762, 763, 765, 768, 769, 771, 772, 774, 777, 778, 779, 780, 781, 784, 786, 787, 788, 791, 792, 794, 796, 797, 799, 804, 805, 807, 813, 816, 817, 819, 822, 823, 825, 826, 829, 831, 832, 835, 838, 839, 840, 846, 847, 848, 850, 852, 853, 855, 856, 859, 861, 862, 864, 865, 867, 869, 870, 871, 874, 876, 877, 878, 883, 884, 887, 891, 892, 893, 895, 896, 900, 903, 906, 914, 915, 916, 917, 918, 919, 922, 925, 927, 928, 929, 930, 936, 938, 941, 945, 946, 947, 949, 951, 952, 954, 955, 958, 960, 961, 963, 964, 966, 967, 968, 969, 971, 972, 974, 976, 977, 979, 981, 982, 983, 985, 986, 991, 992, 994, 996, 997, 999]
[ 3, 3, 3, 3, 3, 2, 10, 14, 10, 3, 10, 14, 3, 2, 14, 10, 3, 14, 10, 2, 10, 2, 10, 14, 10, 10, 10, 14, 10, 2, 10, 10, 3, 10, 3, 3, 3, 2, 2, 3, 2, 10, 10, 10, 14, 10, 3, 14, 10, 14, 10, 3, 10, 10, 10, 3, 10, 14, 10, 10, 14, 2, 10, 3, 3, 2, 3, 2, 10, 10, 10, 2, 10, 10, 14, 10, 10, 10, 3, 10, 14, 6, 14, 14, 6, 10, 14, 14, 10, 2, 2, 2, 3, 14, 10, 2, 3, 10, 3, 10, 10, 10, 14, 10, 14, 14, 3, 14, 10, 10, 14, 14, 10, 10, 10, 10, 10, 10, 10, 10, 14, 10, 3, 10, 14, 3, 2, 10, 10, 10, 3, 2, 10, 10, 10, 10, 2, 3, 10, 3, 10, 10, 10, 10, 10, 14, 3, 10, 10, 14, 10, 14, 10, 10, 3, 14, 10, 10, 10, 14, 10, 10, 14, 10, 10, 3, 10, 3, 3, 10, 3, 2, 14, 10, 14, 10, 2, 10, 10, 14, 10, 10, 14, 10, 10, 10, 14, 10, 10, 10, 14, 10, 3, 14, 10, 14, 2, 10, 14, 10, 14, 10, 2, 6, 10, 10, 14, 10, 10, 10, 6, 2, 14, 3, 14, 3, 14, 10, 2, 10, 2, 3, 14, 10, 14, 10, 10, 14, 14, 3, 14, 10, 10, 14, 10, 10, 3, 14, 3, 14, 10, 14, 2, 10, 2, 10, 14, 6, 14, 14, 14, 10, 10, 2, 14, 14, 2, 14, 10, 10, 14, 3, 14, 10, 14, 10, 14, 10, 10, 10, 3, 10, 10, 10, 10, 3, 10, 14, 6, 14, 14, 10, 10, 10, 10, 10, 14, 10, 10, 14, 10, 14, 10, 2, 6, 14, 10, 10, 2, 14, 14, 14, 10, 14, 10, 10, 6, 10, 6, 14, 14, 10, 10, 14, 10, 2, 10, 10, 3, 10, 14, 10, 10, 14, 14, 6, 10, 10, 10, 10, 10, 14, 10, 10, 3, 10, 10, 10, 14, 10, 10, 10, 6, 2, 2, 14, 10, 10, 14, 3, 10, 10, 6, 10, 6, 10, 10, 10, 2, 3, 2]
Além disso, este é um programa que leva um inteiro \$n\$e, para cada inteiro \$1 \le i \le n\$, gera sua saída e o loop que surge.
Esta é uma pergunta sobre o Math.SE sobre se a saída alguma vez excede \$14\$, e se cada número natural eventualmente entrará em um loop ou não.
Respostas
Haskell , 85 bytes
l=length
k?x|elem x k=l$x:takeWhile(/=x)k|q<-show x=(x:k)?sum[read[k]^l q|k<-q]
([]?)
Experimente online!
Isso é frustrantemente longo para Haskell. Temos uma função principal aqui. Ele mantém o controle de uma lista kde números que já visitamos, acrescentando novos números à frente. Assim que chegarmos a um número xque está em nossa lista, retornamos um a mais do que o maior prefixo que não contém x.
k ? x
| elem x k
=
length (x : takeWhile (/=x) k)
| otherwise
=
(x : k) ? sum [ read [x] ^ length (show x) | k <- show x ]
Python 3 , 107 \$\cdots\$ 90 84 bytes
Salvo um byte graças a Arnauld !!!
f=lambda n,l=[]:n in l and-~l.index(n)or f(str(sum(int(d)**len(n)for d in n)),[n]+l)
Experimente online!
Espera a entrada como uma string.
Jelly , 12 bytes
Eu me pergunto se esta é a mesma resposta de caird (provavelmente não é, porque o fluxo de controle aqui quase certamente pode ser simplificado por qualquer um que realmente conheça Jelly, ou talvez até mesmo por um bom utilitário de compressão sem perdas). Isso também pode estar errado.
D*L$S
ÇÐLÇƬL
Experimente online!
Raku , 67 65 64 bytes
{{$_-1-.first(:k,.tail)}($_,{sum .comb X**.chars}...{%\{$_}++})}
Experimente online!
$_, { ... } ... { ... }gera a sequência de números, começando com$_o argumento para a função externa. As primeiras chaves envolvem a função que gera elementos sucessivos e as segundas chaves envolvem a função que indica quando parar.sum .comb X** .charsproduz o próximo número do precedente. Ocombmétodo sem argumentos divide strings / números em seus caracteres / dígitos. Ocharsmétodo retorna o número de caracteres / dígitos em uma string / número. A lista de dígitos é exponenciada em cruz com o número de dígitos peloX**operador e, em seguida, somada.- A condição final usa uma variável hash de estado anônima
%, que armazena o número de vezes que cada elemento foi visto até agora. A iteração para quando o número atual é visto pela segunda vez. - Essa sequência é alimentada em uma função anônima interna, que é chamada imediatamente. (Isso é um pouco mais curto do que armazenar a sequência em uma variável.) Assim como a função externa, esta função interna aceita seu argumento na
$_variável. .first(:k, .tail)encontra o índice (graças ao:kadvérbio) do primeiro elemento da sequência que é igual ao elemento final, retornado por.tail.$_ - 1 - .first(...)é a duração da sequência, menos um, menos o primeiro índice do único elemento repetido, dando a duração do ciclo final.
Wolfram Language (Mathematica) , 78 73 bytes
-5 graças a J42161217. Sua resposta é melhor, então verifique isso também.
#[]//.a_@e___/;a!=e:>a~Tr[#^#2&@@RealDigits@a]~e/.a_@e__:>{e}~Position~a&
Experimente online!
Husk , 12 bytes
LUṠ-U¡λṁ^L¹d
Experimente online!
Encontrou uma maneira melhor de fazer isso removendo o prefixo exclusivo mais longo da lista infinita e tomando o prefixo exclusivo mais longo desse.
Husk , 14 bytes
▼mLUmUṫ¡λṁ^L¹d
Experimente online!
Basicamente, fazemos uma lista infinita de listas infinitas para descobrir qual delas contém o ciclo necessário. Em seguida, medimos a duração do ciclo.
Explicação
▼mLUmUṫ¡λṁ^L¹d
¡λ apply the following to get an infinite list
d take the digits
^L¹ the the power of their length
ṁ sum them
ṫ get the postfixes of the list
mU get the logest unique prefix of each postfix
U get the longest unique prefix of that
mL Map each cycle to it's lenght
▼ take the minimum
C (gcc) , 202 ... 149 bytes
f(l){long a[16]={},i,k=l,n;for(;i=k;a[n++&15]=k){for(l=0;k;k/=10)l++;for(;i;i/=10)k+=__builtin_powi(i%10,l);for(l=16;l--;)if(a[l]==k)return n-l&15;}}
Experimente online!
Explicado
f(l) {
long a[16] = {}, // Circular buffer of recently seen values
i, // Current value, will be initialized to l,
// l will become number of digits in i,
// and will later be used as a loop counter
k = l, // Will become f(i)
n; // Current index into the circular buffer
for (; i = k; // Loop forever, let i = f(i)
a[n++ & 15] = k) { // Store f(i) in the buffer
for (l = 0; k; k /= 10) // Set length to zero, loop over all digits in k (which is equal to i)
l++; // Increment l for each digit
// k is zero after this loop
for (; i; i /= 10) // Loop over all digits again
k += __builtin_powi(i % 10, l); // Add pow(digit, length) to k
for (l = 16; l--;) // Check all the values in the buffer
if (a[l] == k) // If k matches a value in the buffer
return n - l & 15; // Return the distance between k and the match in the buffer
}
}
Linguagem Wolfram (Mathematica) , 70 59 bytes
Gather@NestList[Tr[#^#2&@@RealDigits@#]&,#,#]~Count~{_,__}&
Experimente online!
-11 bytes de @att
Carvão , 27 bytes
ＮθＷ¬№υθ«⊞υθ≔ΣＸ↨θχＬθθ»Ｉ⊕⌕⮌υθ
Experimente online! O link é para a versão detalhada do código. Explicação:
Ｎθ
Entrada n.
Ｗ¬№υθ«
Repita até que um loop seja detectado.
⊞υθ
Salve o valor anterior.
≔ΣＸ↨θχＬθθ
Calcule o próximo valor.
»Ｉ⊕⌕⮌υθ
Produza o número de termos no loop.
JavaScript (ES7), 72 bytes
Espera o número de entrada como uma string.
n=>(g=i=>i-g[[...n].map(d=>t+=d**n.length,t=0)|t]||g(-~i,g[n=t+'']=i))``
Experimente online!
Comentou
n => ( // n = input number as a string
g = i => // g is a recursive function taking a counter i
i - // subtract from i
g[ // lookup in g:
[...n].map(d => // for each digit d in n:
t += // add to t:
d ** n.length, // d raised to the power of the length of n
t = 0 // starting with t = 0
) | t // end of map(); yield t
] // end of lookup in g
|| // if the above result is NaN,
g( // do a recursive call:
-~i, // pass i + 1
g[n = t + ''] = i // copy t to n, coerced back to a string
// and set this entry to i in g
) // end of recursive call
)`` // initial call to g with i zero'ish
Brachylog , 27 bytes
{tgjlᵗgᵗz^ᵐ+}ᵃ↖N{¬≠&}↔a↰₄bl
Experimente online!
{tgjlᵗgᵗz^ᵐ+}ᵃ↖N{¬≠&}↔a↰₄bl
{ }ᵃ↖N repeat the predicate N times
and accumulate results
tg last result as list [x]
jlᵗgᵗ [x, [len(x)]]
z^ᵐ each digit ^ length
+ sum
{­&} must have duplicates (not all are different)
↔a reverse and take prefixes (shortest first)
↰₄ that must have duplicates
bl length - 1
MATL , 19 bytes
`XIvIFYAtn^syy-]=Pf
Experimente online! Ou plote a sequência de 50a 170(leva cerca de 30 segundos).
Explicação
` % Do...while
XI % Copy into clipboard I. This implicitly takes input the first time
v % Concatenate stack contents vertically. This attaches the newly computed
% term onto the sequence. The first time it does nothing
I % Paste from clipboard I. This pushes the last computed term
FYA % Convert number to vector of decimal digits
tn^s % Duplicate, number of elements, element-wise power, sum. This computes a
% new term to extend the sequence
yy % Duplicate top two elements in the stack: sequence so far and new term
- % Element-wise difference. This is truthy if all values are nonzero
] % End. A new iteration is run if top of the stack is truthy
= % (The stack contains the computed sequence and a new term that has been
% found to appears in that sequence) Element-wise equality comparison
P % Reverse
f % index of true value. Implicitly display
Jelly , 11 bytes
D*L$SƊƬ⁺€ṪL
Experimente online!
D Take the decimal digits
* to the power of
L the length of
$ the list of decimal digits
S and sum them.
Ɗ For all that,
Ƭ iterate until a loop is reached collecting all intermediate results,
€ then for each of the collected results
⁺ iterate again starting from there,
Ṫ take the results from the last result,
L and get the length of that.
Pode ser ainda mais curto se considerarmos a entrada como uma lista de dígitos:
Gelatina , 10 bytes
*LSDƲƬ⁺€ṪL
Experimente online!
Jelly , 11 bytes
Acontece que obtive o mesmo que String não relacionada .
D*L$SƊƬ⁺€ṪL
Um Link monádico que aceita um número inteiro positivo que produz um número inteiro positivo.
Experimente online!
Quão?
D*L$SƊƬ⁺€ṪL - Link: n
Ƭ - collect while distinct:
Ɗ - last three links as a monad:
D - digits
$ - last two links as a monad:
L - length
* - exponentiate
S - sum
€ - for each:
⁺ - repeat the last link (the collect-while-distinct, above)
Ṫ - tail (this will be a single loop)
L - length
05AB1E , 15 bytes
Δ¤SDgmO©ªÙ}R®k>
Experimente online!
Aceita a entrada como uma lista de singleton contendo o inteiro.
Uma abordagem diferente que vem em 16 bytes:
λSDgmO}ηíεćk}Ù¥н
Experimente online!
Comentado :
Δ¤SDgmO©ªÙ}R®k> # implicit input: [x]
Δ } # run until the output does not change:
¤ # take the last integer from the list
S # split into digits
D # duplicate
g # take the length of the copy
m # take each digit to the power of the length
O # sum all powers
© # store this value in the register
ª # and append it to the list
Ù # uniquify the list
# the loop only stops if Ù removed the new element,
# which only happens if it was in the list already
R # reverse the (unique) list
® # take the last computed value
k # find the 0-based index in the list
> # and increment it
λSDgmO}ηíεćk}Ù¥н # implicit input: x
λ } # recursively apply the code to the input
# to generate an infinite list
SDgmO # same as above
η # take the prefixes
í # reverse each prefix
ε } # map over the reversed prefixed
ć # extract the first element
k # find its index in the remaining prefix
# this returns -1 if the prefix was unique
# this results in [-1, ..., -1, res-1, res-1, ...]
Ù # uniquify => [-1, res-1]
# while this list is finite, 05ab1e does not know this
¥ # take the differences => [(res-1) - (-1)] = [res]
н # take the first element => res
APL (dzaima / APL) , 30 29 bytes
{1⊃⍸⌽(⊢/=⊢){+/(⊢*≢)10⊤⍵}⍡⍵⊢⍵}
Experimente online!
-1 byte usando ⎕IO←0.
Uma vez que a duração do ciclo nunca excede \$n\$, podemos fazer loops n vezes em vez de encontrar um ponto fixo e então calcular a duração do ciclo.
Explicação
{⊃⍸1↓⌽(⊢/=⊢){+/(⊢*≢)10⊤⍵}⍡⍵⊢⍵}
⊢⍵ input integer n
{ }⍡⍵ apply the following n times, collecting intermediate results:
10⊤⍵ get base 10 digits
(⊢*≢) raise to the power of length
+/ and sum
(⊢/=⊢) bit mask of the locations of the last element
1↓⌽ reverse and remove first 1
⊃⍸ first index of the last element
Ícone , 99 bytes
procedure f(n)
t:=table()
i:=1
until\t[n]do{t[n]:=i
(s:=0)+:=!n^*n&\z
n:=s
i+:=1}
return i-t[n]
end
Experimente online!
Vermelho , 125 bytes
func[n][m: copy #()i: 1 while[not m/:n][put m n i i: i + 1 s: 0
foreach d k: to""n[s:(-48 + d)**(length? k)+ s]n: s]i - m/:n]
Experimente online!
Scala, 117 bytes
Resposta de Haskell do Mago do Porto de Trigo .
def>(n:Any,k:Seq[_]=Nil):Any=if(k toSet n)1+k.indexOf(n)else>(s"$n".map(d=>math.pow(d-48,s"$n".size).toInt).sum,n+:k)
Experimente online!
Scala, 160 bytes
Stream.iterate(_){n=>s"$n".map(d=>math.pow(d-48,s"$n".size).toInt).sum}.scanLeft(Seq[Int]())(_:+_).flatMap(_.tails).find(l=>l.size>1&&l.head==l.last).get.size-1
Experimente online!
Uma solução ridiculamente longa, agravada pelo fato de que Scala não tem **como Python e outras linguagens fazem, e initsretorna os maiores inits primeiro, então temos que usar scanLeft(Seq[Int]())(_:+_).
R , 84 bytes
x=scan();while(!(y=match(x,F,0))){F=c(x,F);x=sum((x%/%10^((z=nchar(x)):0)%%10)^z)};y
Experimente online!
Comentado:
x=scan(); # get input as x
# F is vector that holds values of f(x) so far
# (initialized by default as zero)
while(!(y=match(x,F,0))){ # if x is present in F, get its matching index as y,
# otherwise set y to zero.
# While !y (x not present in F yet):
F=c(x,F); # prepend F with x
x=sum((x%/%10^((z=nchar(x)):0)%%10)^z) # update x as f(x):
# sum of decimal digits to the power of # digits
};
y # We exit the while loop when F contains x;
# at this point, y gives the index, which is the
# loop length
K (Kona) , 42 bytes
--/&{x=*|x}{x~?x}{x,_+/{x^'#x}10_vs*|x}/,:
Experimente online!
J , 40 bytes
-5 por FrownyFrog!
0(i.~~:@|.)(,*/@~:$1#.&(^#)10#.inv{:)^:_
Experimente online!
J , 45 bytes
[:#.~[:~:&.|.(,1#.&(^#)10#.inv{:)^:(*/@~:)^:_
Experimente online!
…^:_até que o resultado não mude:…^:(*/@~:)se não houver duplicata na lista:10#.inv{:dígitos do último número ...1#.&(^#)alimentado por seu comprimento, somado,anexado à lista.[:~:&.|.lista reversa, obter uma máscara de bits das primeiras ocorrências nela, reverter de volta. Então1 2 3 2 3 -> 3 2 3 2 1 -> 1 1 0 0 1 -> 1 0 0 1 1.[:#.~conte os 1s à direita com conversão de base mista.