Độ dài vòng lặp Narcissistic
Một số tự mãn là một số tự nhiên mà là bằng tổng các chữ số của nó khi mỗi chữ số được đưa đến sức mạnh của các chữ số số. Ví dụ \$8208 = 8^4 + 2^4 + 0^4 + 8^4\$, tự ái cũng vậy.
Chúng tôi sẽ xác định một hàm \$f(x)\$như sau, cho một số tự nhiên \$x = d_1d_2\dots d_n\$, ở đâu \$d_i\$là một chữ số duy nhất \$0\$đến \$9\$(do đó \$x\$có \$n\$ chữ số):
$$f(x) = \sum_{i=1}^nd_i^n$$
Trong trường hợp này, một số là tự ái nếu \$f(x) = x\$.
Tuy nhiên, khi chúng tôi áp dụng \$f(x)\$lặp đi lặp lại một số, chúng tôi nhận thấy một mô hình thú vị xuất hiện. Đối với bất kỳ đã cho \$x\$, chuỗi hoặc đạt đến một điểm cố định (tức là một số tự nhiên) hoặc đi vào một vòng lặp cố định lặp lại vô hạn. Ví dụ: lấy ba số nguyên \$x = 104, 127, 370\$:
\$x = 104\$: Ứng dụng lặp lại của \$f(x)\$ dẫn đến chuỗi sau
$$104, 65, 61, 37, 58, 89, 145, 190, 730, 370, 370, ...$$
Ở đây, vòng lặp cuối cùng đạt đến một điểm cố định, \$370\$.
\$x = 127\$: Ứng dụng lặp lại của \$f(x)\$ dẫn đến
$$127, 352, 160, 217, 352, 160, 217, ...$$
Đây, bộ ba \$352, 160, 217\$ lặp lại quảng cáo infinitum
\$x = 370\$: \$x\$ở đây đã là lòng tự ái, vì vậy chuỗi sẽ chỉ là một dòng bất tận của \$370\$S.
Những ví dụ này ghi lại hai kết quả có thể có cho một \$x\$. Bằng cách coi một điểm cố định là một vòng lặp có độ dài \$1\$, bây giờ chúng ta đến nhiệm vụ trong tầm tay:
Cho một số tự nhiên \$n > 0\$, xuất ra độ dài của vòng lặp phát sinh qua ứng dụng lặp đi lặp lại của \$f(n)\$.
Ba ví dụ trên trả về \$1\$, \$3\$và \$1\$tương ứng. Bạn có thể cho rằng tất cả \$n\$cuối cùng nhập một vòng lặp, vòng lặp này dường như là trường hợp cho ít nhất tất cả \$n < 10^4\$. Nếu tồn tại một \$n\$mà điều này là sai, chương trình của bạn có thể thực hiện bất kỳ điều gì thiếu sót khi triệu hồi Cthulhu .
Đây là mã-gôn nên mã ngắn nhất tính bằng byte sẽ thắng.
Phần lớn các số trả về \$1\$. Tuy nhiên, hai mảng này chứa tất cả \$n < 1000\$ mà không, cùng với kết quả đầu ra của chúng phải là gì:
[ 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]
Hơn nữa, đây là một chương trình lấy một số nguyên \$n\$và, với mỗi số nguyên \$1 \le i \le n\$, tạo ra đầu ra của nó và vòng lặp phát sinh.
Đây là một câu hỏi trên Math.SE về việc liệu đầu ra có bao giờ vượt quá \$14\$, và nếu mỗi số tự nhiên cuối cùng sẽ đi vào một vòng lặp hay không.
Trả lời
Haskell , 85 byte
l=length
k?x|elem x k=l$x:takeWhile(/=x)k|q<-show x=(x:k)?sum[read[k]^l q|k<-q]
([]?)
Hãy thử nó trực tuyến!
Điều này thật khó chịu đối với Haskell. Chúng tôi có một chức năng chính ở đây. Nó theo dõi danh sách kcác số chúng tôi đã truy cập, thêm các số mới vào phía trước. Khi chúng tôi đạt đến một số xcó trong danh sách của chúng tôi, chúng tôi trả về một số nhiều hơn tiền tố lớn nhất không chứa 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 byte
Đã lưu một byte nhờ 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)
Hãy thử nó trực tuyến!
Mong đợi đầu vào là một chuỗi.
Thạch , 12 byte
Tôi tự hỏi liệu điều này có giống với câu trả lời của caird hay không (có lẽ là không, bởi vì luồng điều khiển ở đây gần như chắc chắn có thể được đơn giản hóa bởi bất kỳ ai thực sự biết Jelly, hoặc thậm chí có thể bằng một tiện ích nén không mất dữ liệu tốt). Điều này cũng có thể sai.
D*L$S
ÇÐLÇƬL
Hãy thử nó trực tuyến!
Raku , 67 65 64 byte
{{$_-1-.first(:k,.tail)}($_,{sum .comb X**.chars}...{%\{$_}++})}
Hãy thử nó trực tuyến!
$_, { ... } ... { ... }tạo dãy số, bắt đầu bằng$_, đối số cho hàm bên ngoài. Dấu ngoặc nhọn đầu tiên bao quanh hàm tạo ra các phần tử kế tiếp và dấu ngoặc thứ hai bao quanh hàm cho biết thời điểm dừng.sum .comb X** .charstạo ra số tiếp theo từ số trước đó. Cáccombphương pháp không có đối số chia tách chuỗi / số vào nhân vật của họ / chữ số. Cáccharsphương thức trả về số ký tự / chữ số trong một chuỗi / số. Danh sách các chữ số được lũy thừa chéo với số chữ số bởiX**toán tử, sau đó được cộng lại.- Điều kiện kết thúc sử dụng một biến băm trạng thái ẩn danh
%, biến này lưu trữ số lần từng phần tử được nhìn thấy cho đến nay. Việc lặp lại dừng khi số hiện tại được nhìn thấy lần thứ hai. - Chuỗi đó được đưa vào một hàm ẩn danh bên trong, hàm này được gọi ngay lập tức. (Điều này ngắn hơn một chút so với việc lưu trữ chuỗi thành một biến.) Cũng giống như hàm bên ngoài, hàm bên trong này chấp nhận đối số của nó trong
$_biến. .first(:k, .tail)tìm chỉ số (nhờ:ktrạng từ) của phần tử đầu tiên của dãy bằng với phần tử cuối cùng, trả về bởi.tail.$_ - 1 - .first(...)là độ dài của dãy, trừ đi một, trừ đi chỉ số đầu tiên của phần tử lặp lại đơn lẻ, cho độ dài của chu kỳ cuối cùng.
Ngôn ngữ Wolfram (Mathematica) , 78 73 byte
-5 nhờ J42161217. Câu trả lời của anh ấy là tốt hơn, vì vậy hãy kiểm tra điều đó.
#[]//.a_@e___/;a!=e:>a~Tr[#^#2&@@RealDigits@a]~e/.a_@e__:>{e}~Position~a&
Hãy thử nó trực tuyến!
Husk , 12 byte
LUṠ-U¡λṁ^L¹d
Hãy thử nó trực tuyến!
Đã tìm thấy một cách tốt hơn để làm điều đó bằng cách xóa tiền tố duy nhất dài nhất khỏi danh sách vô hạn và lấy tiền tố duy nhất dài nhất trong số đó.
Husk , 14 byte
▼mLUmUṫ¡λṁ^L¹d
Hãy thử nó trực tuyến!
Về cơ bản, chúng tôi tạo một danh sách vô hạn các danh sách vô hạn để tìm cái nào chứa chu trình bắt buộc. Sau đó, chúng tôi lấy độ dài của chu kỳ.
Giải trình
▼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 byte
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;}}
Hãy thử nó trực tuyến!
Giải thích
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
}
}
Ngôn ngữ Wolfram (Mathematica) , 70 59 byte
Gather@NestList[Tr[#^#2&@@RealDigits@#]&,#,#]~Count~{_,__}&
Hãy thử nó trực tuyến!
-11 byte từ @att
Than củi , 27 byte
ＮθＷ¬№υθ«⊞υθ≔ΣＸ↨θχＬθθ»Ｉ⊕⌕⮌υθ
Hãy thử nó trực tuyến! Liên kết là phiên bản dài của mã. Giải trình:
Ｎθ
Đầu vào n.
Ｗ¬№υθ«
Lặp lại cho đến khi một vòng lặp được phát hiện.
⊞υθ
Lưu giá trị trước đó.
≔ΣＸ↨θχＬθθ
Tính giá trị tiếp theo.
»Ｉ⊕⌕⮌υθ
Xuất ra số hạng trong vòng lặp.
JavaScript (ES7), 72 byte
Mong đợi số đầu vào là một chuỗi.
n=>(g=i=>i-g[[...n].map(d=>t+=d**n.length,t=0)|t]||g(-~i,g[n=t+'']=i))``
Hãy thử nó trực tuyến!
Đã nhận xét
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 byte
{tgjlᵗgᵗz^ᵐ+}ᵃ↖N{¬≠&}↔a↰₄bl
Hãy thử nó trực tuyến!
{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 byte
`XIvIFYAtn^syy-]=Pf
Hãy thử nó trực tuyến! Hoặc vẽ theo trình tự từ 50đến 170(mất khoảng 30 giây).
Giải trình
` % 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
Thạch , 11 byte
D*L$SƊƬ⁺€ṪL
Hãy thử nó trực tuyến!
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.
Thậm chí có thể ngắn hơn nếu chúng ta lấy đầu vào là danh sách chữ số:
Thạch , 10 byte
*LSDƲƬ⁺€ṪL
Hãy thử nó trực tuyến!
Thạch , 11 byte
Hóa ra tôi nhận được giống như Chuỗi không liên quan .
D*L$SƊƬ⁺€ṪL
Một Liên kết đơn nguyên chấp nhận một số nguyên dương tạo ra một số nguyên dương.
Hãy thử nó trực tuyến!
Làm sao?
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 byte
Δ¤SDgmO©ªÙ}R®k>
Hãy thử nó trực tuyến!
Nhận đầu vào dưới dạng một danh sách đơn lẻ chứa số nguyên.
Một cách tiếp cận khác có dung lượng 16 byte:
λSDgmO}ηíεćk}Ù¥н
Hãy thử nó trực tuyến!
Đã nhận xét :
Δ¤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 byte
{1⊃⍸⌽(⊢/=⊢){+/(⊢*≢)10⊤⍵}⍡⍵⊢⍵}
Hãy thử nó trực tuyến!
-1 byte bằng cách sử dụng ⎕IO←0.
Vì độ dài của chu kỳ không bao giờ vượt quá \$n\$, chúng ta có thể lặp n lần thay vì tìm một điểm cố định, sau đó tính độ dài của chu trình.
Giải trình
{⊃⍸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
Biểu tượng , 99 byte
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
Hãy thử nó trực tuyến!
Đỏ , 125 byte
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]
Hãy thử nó trực tuyến!
Scala, 117 byte
Câu trả lời Haskell của phù thủy Port of Wheat .
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)
Hãy thử nó trực tuyến!
Scala, 160 byte
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
Hãy thử nó trực tuyến!
Một giải pháp dài kỳ cục, tệ hơn vì Scala không có **như Python và các ngôn ngữ khác, và initstrả về các inits lớn nhất trước tiên, vì vậy chúng ta phải sử dụng scanLeft(Seq[Int]())(_:+_).
R , 84 byte
x=scan();while(!(y=match(x,F,0))){F=c(x,F);x=sum((x%/%10^((z=nchar(x)):0)%%10)^z)};y
Hãy thử nó trực tuyến!
Đã nhận xét:
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 byte
--/&{x=*|x}{x~?x}{x,_+/{x^'#x}10_vs*|x}/,:
Hãy thử nó trực tuyến!
J , 40 byte
-5 bởi FrownyFrog!
0(i.~~:@|.)(,*/@~:$1#.&(^#)10#.inv{:)^:_
Hãy thử nó trực tuyến!
J , 45 byte
[:#.~[:~:&.|.(,1#.&(^#)10#.inv{:)^:(*/@~:)^:_
Hãy thử nó trực tuyến!
…^:_cho đến khi kết quả không thay đổi:…^:(*/@~:)nếu không có bản sao trong danh sách:10#.inv{:chữ số của số cuối cùng…1#.&(^#)được cung cấp bởi chiều dài của chúng,,được thêm vào danh sách.[:~:&.|.đảo ngược danh sách, nhận một mặt nạ bit của lần xuất hiện đầu tiên trong đó, đảo ngược trở lại. Vì vậy1 2 3 2 3 -> 3 2 3 2 1 -> 1 1 0 0 1 -> 1 0 0 1 1.[:#.~đếm số 1 ở cuối với chuyển đổi cơ sở hỗn hợp.