![]() |
math problem using recursion? - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: Homework (https://python-forum.io/forum-9.html) +--- Thread: math problem using recursion? (/thread-29418.html) Pages:
1
2
|
math problem using recursion? - mnh001 - Sep-01-2020 First the problem. 1. Start with a semi-prime (eg, 15 = 3 * 5). 2. Take the factors and concatenate them both forwards and backwards to give 2 new numbers. (Ie, 35 and 53) 3. Test for semi-prime-ness. If semi-prime, go to step 2. If not, end that branch. The process ends when no further semi-primes are generated. This creates a tree of numbers. The tree is built as you go from the top down. See image for the tree of 15. [attachment=978] For 15 the length of the chain of semi-primes is 7. The object is to find the start number with the longest chain of semi-primes. I "think" this might be a good place to use recursion. However, I've never done recursion and only have a hazy grasp of it. I've seen a few videos about it but they either don't show an example or the examples they give are for factorials or Fibonacci. Neither of which seems to be of help with this problem. To get the semi-primes themselves and their factors I thought I could either calculate them on the fly or pre-compute them and put them into a list or dictionary or something. But as for the recursion part how would this problem be coded in Python? TIA RE: math problem using recursion? - DPaul - Sep-01-2020 Before we do any recursion stuff, if necessary, maybe you could write a function to find al the divisors of a given number. That is 50% of the work done. The longest chain length could be millions , no ? Or is the start number limited? Paul RE: math problem using recursion? - Larz60+ - Sep-01-2020 Give it a go, and when you have a specific problem, show your code and we will be glad to help. RE: math problem using recursion? - mnh001 - Sep-01-2020 Sure. Ok, here's some code. I know it's not pretty and it still needs some fixing but it seems to work good enuf for testing purposes. This creates a dictionary of semi-primes and their factors. sp_dict = {} primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] def semi(): for i in range(9, 101, 2): #for the real thing this range will be much larger divisors = [] for j in primes: if j > math.sqrt(i): continue else: div = i / j if div == int(div): divisors.append(j) divisors.append(div) if len(divisors) == 2: value = "(" + str(divisors[0]) + ", " + str(int(divisors[1])) + ")" sp_dict[i] = value print(sp_dict) a = semi()I haven't yet got the code to pull the info out of the dictionary. Still working on that. (OBTW, while I am still learning Python, this is not homework. I found this problem on another website, thought it looked interesting and decided to try to figure out how to program it.) RE: math problem using recursion? - mnh001 - Sep-01-2020 As for the previous questions, the only requirement for the start number is that it is a semi-prime. And I doubt whether the chain lengths would ever get above 20 or 30. Ok, here is my revised code. I fixed the previous errors. I've added the routine to pull out the data from the dictionary and create the new numbers. But I don't really know where to go from here. import math sp_dict = {} primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] def semi(): for i in range(9, 101, 2): #for the real thing this range will be much larger divisors = [] for j in primes: if j > math.sqrt(i): continue else: div = i / j if div == int(div): b = div / j if b == int(b) and b > 1: continue else: divisors.append(j) divisors.append(div) if len(divisors) == 2: value = "[" + str(divisors[0]) + ", " + str(int(divisors[1])) + "]" sp_dict[i] = value print() print(sp_dict) print() # checks dictionary for entry. if there, pulls out factors # and assigns to variables def check_if_sp(n): if n in sp_dict: x = sp_dict[n] x = x.strip('[') x = x.strip(']') x = x.split(', ') fact1 = x[0] fact2 = x[1] print(f'{n} = {fact1} * {fact2}') return fact1, fact2 else: print(n,' is not a semi-prime.') a = semi() n = int(input('Input a number: ')) fact1, fact2 = check_if_sp(n) # creates 2 new numbers from the factors to check new1 = int(fact1 + fact2) new2 = int(fact2 + fact1) print(f'New numbers are {new1} and {new2}')Ok, how do I proceed to create the tree as in the image in the first post? RE: math problem using recursion? - DPaul - Sep-02-2020 The numbers in your sample tree are correct, but the 000 separator looks sometimes like a decimal point , a bit confusing, but it is to show concatenation. I'm not sure how to proceed in this homework section, because my approach is quite different. If the purpose is to use recursion, i see no need for it, but a python "evangelist" might. :-) I also see no need for the dictionary , nor the list of primes e.g. to find the divisors of a number, i use this: def divisors(x): div = [] for i in range(2,int(x/2)+1): if x % i == 0: div.append(i) if len(div) == 2: print(f'Divisors of {x}', div) new_numbers(div) else: print(f'{x} is Not Semi Prime')I assume by your definition that a semiprime can only have 2 divisors, both prime. We also assume that the seed number is semi-prime, although if it is not, the iterations will stop soon enough. the new_numbers() function generates 'xy' and 'yx', that are added to a list. You then call divisors() for the listed results. Paul
RE: math problem using recursion? - mnh001 - Sep-02-2020 Ok, first, it is a decimal point. I was only using it to delineate between the factors for visual clarity. Next, I didn't know if this was a good problem for recursion. I was kinda hoping it was just so I can get some experience with recursion. But if it doesn't need it that's ok too. The list of primes is there because when factoring the only numbers needed to check for divisibility are the primes up to the square root of the original number. And since Python doesn't seem to have any prime routines I had to add the list. Normally when working with primes I use UBasic but since I'm trying to learn Python... True, I suppose I didn't really need the dictionary. I could just compute on the fly but this way I could 'see' things better. Yes, I believe I mentioned earlier that the seed number is a semi-prime. And a semi-prime is indeed a number with only 2 factors (excluding 1 and the number itself). I tried your code (adding a couple of lines for initial input) but got an error. I take it there's more to it than what you showed?
RE: math problem using recursion? - DPaul - Sep-02-2020 Yes there is some more code, but if i go ahead and post everything i will get my *** kicked. Moderators have short fuses here. :-) This is the code up to the while True loop: (only 5 more lines after that) def divisors(x): div = [] for i in range(2,int(x/2)+1): if x % i == 0: div.append(i) if len(div) == 2: print(f'Divisors of {x}', div) new_numbers(div) else: print(f'{x} is Not Semi Prime') def new_numbers(n): global newList newList.append(int(str(n[0]) + str(n[1]))) newList.append(int(str(n[1]) + str(n[0]))) print('New numbers:', newList[-1], newList[-2]) start_num = 15 print('Start:', start_num) newList = [] divisors(start_num) passes = 0 while True:The idea is to append all the numbers to be investigated to a list ("newList"); Then in the while loop, you test each one for semi_prime. "passes" is an index for "newList" that you increment. All this in a try..;except, to avoid list index violations. paul RE: math problem using recursion? - bowlofred - Sep-02-2020 A big post that is self-contained and easily runnable to show the output or error is much better than a small post that leaves something out or can't be run. RE: math problem using recursion? - mnh001 - Sep-02-2020 Ok, let me try to work that out. One thing I like already that I had forgotten all about is the mod operator. Have no idea why I didn't think of that. Anyway I'll get back once I get something that works. |