Period of the decimal representation
APL, 19 chars/bytes*
{(↑⍳⍨1∘↓)⌽⍵|10x*⍳⍵}
Nars2000. The previous version was wrong on some numbers, this should be right. I manually checked it on all numbers up to 50.
Again, credit goes to Ben Reich for the idea of looking at the period of 10^i (mod x)
Exploded view
{ ⍳⍵} generate all naturals up to the argument ⍵
10x* raise 10 to each of them, with unlimited precision
⍵| compute the respective remainders mod ⍵
⌽ reverse the list
( ⍳⍨ ) (fork) find the position of the first occurrence
↑ of the fist element of the list
1∘↓ in the remainder of the list
Examples
{(↑⍳⍨1∘↓)⌽⍵|10x*⍳⍵}¨1 2 3 7 13 14 123 345 654 12345 67890
1 1 1 6 6 6 5 22 108 822 120
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
*: APL can be written in its own (legacy) single-byte charset that maps APL symbols to the upper 128 byte values. Therefore, for the purpose of scoring, a program of N chars that only uses ASCII characters and APL symbols can be considered to be N bytes long.
GolfScript (42 27)
{:x)1\[{.10*x%}*]-1%(?)}:P;
Benchmark time: 5 secs. Benchmarking code:
'"The time is #{Time.now#1
}"'~ puts
[1 2 3 7 13 14 123 345 654 12345 67890 99991]{[P]p}%
'"The time is #{Time.now#2
}"'~ puts
Credit to Ben Reich for the core idea of looking at the period of 10^i (mod x).
Explanation
The period p is defined as the smallest positive integer such that for all sufficiently large i we have frac(10^i * 1/x) = frac(10^(i+p) * 1/x). We can simplify that slightly to frac(10^i / x) = frac(10^(i+p) / x). Now, frac(a / x) = frac(b / x) iff a == b (mod x), so we're looking for the smallest positive integer such that for all sufficiently large i: 10^i == 10^(i+p) (mod x).
Suppose 10^i == 10^(i+p) (mod x). Then 10^(i+1) == 10 * 10^i == 10 * 10^(i+p) == 10^(i+p+1) (mod x); so once we get a repetition, we're in an unbreakable cycle.
There are only x distinct values (mod x), so by the pigeonhole principle we must get a repetition in the first x + 1 values of 10^i (mod x).
So what the code above does is to compute x + 2 values of 10^i (mod x)*. Then the last one is guaranteed to be a repetition, and by reversing the list and searching for it I can find the most recent occurrence. Moreover, because I'm only doing the one search this is pseudolinear time.
* The extra one is to handle the special case x = 1, because I don't reduce 10^0 (mod x) and so I'd be looking for a 0 in [1].
Golfscript - 26 bytes
{:i.)+.,{;10*i%.}%i>|,}:f;
Edit: updated to output 1 if the decimal terminates, rather than the length of the decimal representation.
A fairly efficient version. The value 67890 runs in approximately 10 seconds, and 99991 around 20 seconds. It's a bit slower than it was before (roughly half as fast), because the range that is iterated has been doubled, the first half of which is ignored.
Alternative, also 26 bytes
{:i.)+.n*{*i%.}%i>)^^,}:f;
This one works by iterating over the string "\n"*(2*i+1), where i is the value passed to the function. The value passed to the block each time is the ordinal value of "\n", which is 10.
The )^^ is a bit of a work-around. When you uncons a character from a string, the result is the ordinal value of the character removed, as mentioned above. However, appending that value back on will append the string representation of that number, rather than the character - fairly nonsymmetric behavior, and in my opinion a design flaw. If you actually wanted to do that, stringifying first would only cost one byte.
An extra copy of the final value is already on the stack, so I remove the final value again ), xor it with the string, and then xor it again, so that any characters which were added or removed by the first xor are restored. If int op string were treated as a character, rather than its string representation, )^^ could be replaced by |.
Note that while strings (which in Golfscript are stored as an array of ints) will display the value of each character mod 256, the values of each character may themselves be outside this range. When testing for uniqueness (via set operations) or containedness (via ?), it is the actual value that is compared, rather than the display value.
A patch file for the current Golfscript interpreter:
61c61
< to_gs
---
> Gstring.new([self])
The above will only affect the behavior of string op int (and vice versa), where op is one of
+-|&^. Everything else remains unaffected, including the behavior of Gint`.
The following 24 byte solution would then become valid:
{:i.)+.n*{*i%.}%i>|,}:f;
And this also fixes a lot of other really ugly work-arounds.
Python - 48 bytes
f=lambda n:len(set(10**-~i%n for i in range(n)))
Not the most efficient solution, but reasonable for values less than 100000.
FWIW, the core element is identical to my solution for Generate cyclic numbers in decimal.
A more efficient version of the same code (70 bytes):
def f(n):
a=[];i=10%n
while i not in a:a+=i,;i=i*10%n
return len(a)
The value 99991 takes less than a second.