20
2
When you look at the last decimal digit of each power of a non-negative integer a repeating pattern forms. For example, 3:
3^1 = 3
3^2 = 9
3^3 = 27
3^4 = 81
3^5 = 243
3^6 = 729
3^7 = 2187
3^8 = 6561
3^9 = 19683
The last digits go 3971
which repeats indefinitely. In fact any number we choose that ends in 3 has that same pattern because none of the other digits can have an effect on the ones place during repeated multiplication.
What's curious is that some numbers have a much shorter cycle of power-ending digits. For example with 5 the powers all end in 5 so the pattern, written as short as possible, is simply 5
.
Looking at the minimal power-ending digits patterns for 0 through 9 we get:
0 -> 0
1 -> 1
2 -> 2486
3 -> 3971
4 -> 46
5 -> 5
6 -> 6
7 -> 7931
8 -> 8426
9 -> 91
(The lengths of these being 11442
repeated is a curious tidbit itself.)
Remember, any numbers above 9 will have the same pattern as their last digit as was explained above with 3.
Challenge
Your challenge here is to write a program that takes in any non-negative integer and outputs its minimal power-ending digit pattern.
The exact output formatting, whether string or list, doesn't matter. For example, here are some potential inputs followed by valid potential outputs:
900 -> [0]
11 -> 1
2 -> 2486
303 -> 3, 9, 7, 1
44 -> 4 6
45 -> 5
666 -> "6"
3857 -> [7 9 3 1]
118 -> '8426'
129 -> [9, 1]
The shortest code in bytes wins.
I assume we can't indefinitely print the list? – RGS – 2020-02-02T14:02:53.137
4@RGS No. The point is to just print the minimal sequence of 1, 2, or 4 digits. – Calvin's Hobbies – 2020-02-02T14:03:36.013
5"Your challenge here is to write a program that takes in any non-negative integer and outputs it's minimal power-ending digit pattern" but then "Pretty much reproduce the list above." & [tag:kolmogorov-complexity] - which is it? – Jonathan Allan – 2020-02-02T14:43:40.887
1...I guess the former since you give examples, I suggest removing the KC tag and "Pretty much reproduce the list above." – Jonathan Allan – 2020-02-02T14:52:34.357
@JonathanAllan I figured there could be elements of KC in some solutions since the data is pretty small. And for the inputs 0 to 9 the list would be reproduced. Sorry if that's not clear - I'm open to better phrasing? – Calvin's Hobbies – 2020-02-02T15:11:39.943
4If we want to put this in the math jargon, this is the semigroup generated by $n$ on the monoid $\langle\mathbb{Z}_{10},\times\rangle$. – Post Rock Garf Hunter – 2020-02-02T15:47:27.513
Are we allowed to produce incorrect results upon overflow? – S.S. Anne – 2020-02-02T23:24:47.913
@S.S.Anne Like if the input integer is too big? That's fine. As long as your program can accept integers up to your language's usual maximum, like 2^31-1. – Calvin's Hobbies – 2020-02-03T00:43:50.073
1No, if the calculations of the integers inside the functions are too big. – S.S. Anne – 2020-02-03T00:47:36.567
1@S.S.Anne Ah. Good point. It's ok if things overflow if you're taking powers. – Calvin's Hobbies – 2020-02-03T02:40:02.753
@Calvin'sHobbies: compactly encoding a lookup table can be part of a code-golf answer. That doesn't mean the overall problem is one of Kolmogorov complexity. It's nice that the question points out that the pattern for any number is the pattern for it's lowest decimal digit. Maybe you want to replace some of the other phrasing with that? But @ JonathanAllen already told you how to fix the biggest misleading part: simply remove the sentence "Pretty much reproduce the list above." The test cases are clearer without that. – Peter Cordes – 2020-02-03T10:33:43.547
1@640KB Nope, sorry. – Calvin's Hobbies – 2020-02-04T01:18:06.597