How to write a suitable recurrence relation for a python function?

Question

I have an exercise in which I am require to build a recursive function that takes a natural number and returns "True" if it is divisible by 3, or "False" otherwise, using the 3-divisibility rule. Then I was asked to write a recurrence relation of this function. The function I wrote is:

def divide3(n):
 i=0
 while i in range(0,len(str(n))-1):
 if (sum(n, i))%3==0:
 if (divide3(int(str(n)[i+1:])))==True:
 return True
 else:
 return False
 continue

What I don't understand is how I am supposed to write an n-depended recurrence relation, if the number of operations I make is related to the number of digits in n, and has nothing to do with n itself. I would appreciate any help in the subject.

• user40980: I know this is purely tangential... but why not return divide3(int(str(n)[i+1:])) rather than that if block of four lines?
• Meitar: That is a good idea. I shall try this. But it still doesn't get me close to understanding how to write a recurrence relation. Thank you, though.
• Meitar: The problem with what you are suggesting, is that that way there are no executions of "True" of "False"
• user40980: If (divide3(int(str(n)[i+1:]))) returns True (or False), why not just return that than testing to see if it returns True and then returning True (and if not, returning False)? Though again, this gets more into the code review part of the world (and may be a good question to ask on CodeReview.SE once you have complete and working code).

Answer 1

Sorry, but your code doesn't work at all and makes no sense whatsoever. If it gets into the loop at all, it immediately gets killed by an error. Did you even try it? I'd recommend first getting it right instead of trying to come up with a recurrence relation for something broken. Or did they ask you for the recurrence relation because they saw your code and also had no idea what you were doing, so this is their way of trying to get you to explain?

What's "the 3-divisibility rule"? You mean that a number is divisible by 3 if and only if its digit sum is? If so, then that directly tells you what to do: When asked whether some number is divisible by 3 and you don't know right away, ask yourself whether its digit sum is divisible by 3. If that number is still too large to see it directly, ask yourself whether the digit sum of that number is divisible by 3. And so on.

Straight-forward implementation then:

def divide3(n): return n in (0, 3, 6, 9) if n < 10 else divide3(sum(map(int, str(n))))

Bit more interesting:

def divide3(n): return n in (0, 3, 6, 9) if n < 10 else divide3(n//10 + n%10)

(Sorry about the formatting, don't know how to spoilerize code.)

• Meitar: What I finally wrote is: def div3(n): if len(str(sum(n)))<=1: if n%3==0: return True return False else: return div3(sum(n)) Is it admissible? If so, what could be a suitable recurrence relation? This is where I am having troubles.
• Stefan Pochmann: That throws an error every time. How can you seriously ask whether that is admissible?
• Meitar Abarbanel: It looks at first at the length of the first summation of the number digits. If the sum is one digit, then it checks if it is 0 modulo 3. Otherwise, it applies itself on the sum and so on.