Find smallest period from a >1000 digit number

Your job is to take this number as input (although it should work with any other number too):

18349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957


and find the smallest period, which is in this case:

1834957034571097518349570345710975183495703457109751834957034571097518349570345710976


Good luck and have fun!

Clarifications:

• The input number has in minimum one period and one partial period
• The period always starts at the beginning of the input number
• Period means in this case a sequence of numbers which repeats itself.
• what is the maximum size of the input number? if you meant 1000 is the maximum size, your > is facing the wrong way. – Level River St Sep 22 '14 at 9:52
• @steveverrill: No, there is no maximum size of the input number per se, but let's limit it to 2^16 digits (because you asked). – Michael Bolli Sep 22 '14 at 10:15
• What is a period? – FUZxxl Sep 22 '14 at 12:13
• @FUZxxl in this case: a sequence of numbers which repeats itself. – Michael Bolli Sep 22 '14 at 12:19
• What you're asking for is clear, but you really should not call it a period: in mathematics, a period only refers to digits after the decimal point repeated infinitely many times. As opposite, your test input is an integer and has a finite number of digits. – GOTO 0 Sep 22 '14 at 12:46

CJam, 20 16 bytes

Ll:Q{+_Q,*Q#!}=;


Reads from STDIN. Try it online.

The above code will require O(n2) memory, where n is the length of the input. It will work with 216 digits, as long as you have enough memory.

This can be fixed the the cost of five extra bytes:

Ll:Q{+_Q,1$,/)*Q#!}=;  Example run $ cjam <(echo 'Ll:Q{+_Q,*Q#!}=;') <<< 18349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957; echo
1834957034571097518349570345710975183495703457109751834957034571097518349570345710976
$cjam <(echo 'Ll:Q{+_Q,*Q#!}=;') <<< 12345123451; echo 12345$ cjam <(echo 'Ll:Q{+_Q,*Q#!}=;') <<< 1234512345; echo
12345
$cjam <(echo 'Ll:Q{+_Q,*Q#!}=;') <<< 123451; echo 12345  How it works For input Q, the idea is to repeat the first character len(Q) times and check if the index of Q in the result is 0. If it isn't, repeat the first two characters len(Q) times, etc. L " Push L := []. "; l:Q " Read one line from STDIN and save the result in Q. "; { }= " Find the first element q ∊ Q that yields a truthy value: "; + " Execute L += [q]. "; _Q,*Q# " Push (L * len(Q)).index(Q). "; ! " Compute the logical NOT of the index. "; ; " Discard the last q. This leaves L on the stack. ";  Regex (.NET flavour), 23 22 bytes .+?(?=(.*$)(?<=^\1.*))


This will match the required period as a substring.

Test it here.

How does it work?

# The regex will always find a match, so there's no need to anchor it to
# the beginning of the string - the match will start there anyway.
.+?        # Try matching periods from shortest to longest
(?=        # Lookahead to ensure that what we've matched is actually
# a period. By using a lookahead, we ensure that this is
# not part of the match.
(.*\$)    # Match and capture the remainder of the input in group 1.
(?<=     # Use a lookahead to ensure that this remainder is the same
# as the beginning of the input. .NET lookaheads are best
# read from right to left (because that's how they are matched)
# so you might want to read the next three lines from the
# bottom up.
^      # Make sure we can reach the beginning of the string.
\1     # Match group 1.
.*     # Skip some characters, because the capture won't cover the
# entire string.
)
)

• This only works if the period starts at the beginning of the string, though. That happens to be the case here, but I don't see this in the specs. Right? – Tim Pietzcker Sep 22 '14 at 12:59
• @TimPietzcker See OP's comment/edit on the question: the period always starts at the beginning of the string. – Martin Ender Sep 22 '14 at 15:40
• Regex Storm .Net seems to handle .NET as well, and it doesn't require Silverlight (unavailable on most platforms). – Dennis Sep 22 '14 at 18:11
• @Dennis Thanks, I didn't know that one! – Martin Ender Sep 22 '14 at 18:13
• @tolos That's because you don't ensure that you can reach the end of the string like this. Hence it will just use the first thing that repeats at all. E.g. aabaabaab will probably match a because it repeats. I haven't found a way to solve it in PCRE yet. Dennis tried in a now deleted answer, but that one didn't fully work either. Btw, you don't need g. – Martin Ender Sep 22 '14 at 20:05

Python 60

s is the string of digits

[s[:i]for i in range(len(s))if(s[:i]*len(s))[:len(s)]==s][0]


eg:

>>> s = '18349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957034571097518349570345710975183495703457109761834957034571097518349570345710975183495703457109751834957034571097518349570345710976183495703457109751834957034571097518349570345710975183495703457109751834957034571097618349570345710975183495703457109751834957'
>>> [s[:i]for i in range(len(s))if(s[:i]*len(s))[:len(s)]==s][0]
'1834957034571097518349570345710975183495703457109751834957034571097518349570345710976'


Pyth, 14 characters

hf}z*lzTm<zdUz


Explanation:

implicit:      z = input()
f                  filter(lambda T:
}z                                z in
*lz                                  len(z) *
T                                          T,
m                        map(lambda d:
<zd                                  z[:d],
Uz                                   range(len(d)))))


Essentially, it generates all of the initial sequences of the input, repeats each one len(z) times, and sees whether z, the input, lies within the resultant string.

This is not a valid answer, but a feature was recently added to Pyth, after the question was asked, that allows a 12 character solution:

<zf}z*lz<zT1


This uses the filter on integer feature.

Japt, 8 bytes

å+ æ@¶îX


Try it

-2 bytes thanks to Shaggy!

Transpiled JS Explained:

// U is the input string representation of the number
U
// cumulative reduce using the '+' operator
// the result is an array of strings length 1, 2, ..., N
// all substrings start with the first character from input
.å("+")
// find the first match
.æ(function(X, Y, Z) {
// repeat the substring until it is as long as the input
// and compare it to the input
return U === U.î(X)
})

• 8 bytes: å+ æ@¶îX – Shaggy Mar 24 '19 at 23:52
• Excellent :) I've seen throwing an operator into the reduce function before, but forgot about it. – dana Mar 25 '19 at 3:11

Java 8, 125 bytes

Takes input as a string since there is no reasonable way to represent a 1000+ digit number in Java other than a string (No BigInteger please).

s->{String o="";for(int i=0;java.util.Arrays.stream(s.split(o+=s.charAt(i++))).filter(b->!b.isEmpty()).count()>1;);return o;}


Try it online!

• You can replace String with var. -3 bytes – Adam Mar 25 '19 at 6:24
• @Adam Java 8 though – Benjamin Urquhart Mar 25 '19 at 15:50
• Oh, didn't see that. – Adam Mar 25 '19 at 16:09