Welcome, guest | Sign In | My Account | Store | Cart

Maintain an F.S.A to keep track of the consequent remainders as states, input symbols as driving actions on each state. O(N) is the time complexity to find the given large string [in some radix(R), for some specific divisor(D)], where N is the length of the Input String which confirms to the Language Rules under the alphabet. O(R*D) is the space complexity to keep the F.S.A in memory for lookup!

Python, 16 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def infinite_stream_divisor(base, divisor, stream):
	k = -1
	fsa = {}
	for state in range(divisor): # Does the trick :)
		fsa[state] = []
		for input in range(base):
			k = (k+1) % divisor
			fsa[state].append(k)

	state = 0
	for symbol in stream:
		state = fsa[state][int(symbol)]

	if state == 0:
		return True
	return False

Well, this one needs little more explanation than what was explained. Little understanding of the theory of computation or Finite State Automata theory is enough. Each state(row) holds the remainder upon receiving the input symbol, each symbol(column) represents the target state to change upon the input.

Usage: base = int(raw_input("Enter Number System For the Input Sequence:")) divisor = int(raw_input("Enter the Divisor:")) stream = raw_input("Enter the Sequence:")

if infinite_stream_divisor(base, divisor, stream): print "The string is divisible by ", divisor else: print "The string is not divisible by ", divisor

""" Enter Number System For the Input Sequence:2 Enter the Divisor:3 Enter the Sequence:111 The string is not divisible by 3 """

Related Links: http://en.wikipedia.org/wiki/Divisor_function

1 comment

Narayana Chikkam (author) 11 years, 4 months ago  # | flag

Of course, if we can develope a FSA [or NFA, which can be minimized to an FSA], we can write a regex and do it. http://mathforum.org/kb/message.jspa?messageID=4614160&tstart=0 Solution: http://mathforum.org/kb/message.jspa?messageID=7134648&tstart=0

Thanks.