math problem using recursion?

[mnh001]

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.    

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

[DPaul]

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

[Larz60+]

Give it a go, and when you have a specific problem, show your code and we will be glad to help.

[mnh001]

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.)

[mnh001]

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?

[DPaul]

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

Output:
Start: 15
Divisors of 15 [3, 5]
New numbers: 53 35
Divisors of 35 [5, 7]
New numbers: 75 57
53 is Not Semi Prime
Divisors of 57 [3, 19]
New numbers: 193 319
75 is Not Semi Prime
Divisors of 319 [11, 29]
New numbers: 2911 1129
193 is Not Semi Prime
1129 is Not Semi Prime
Divisors of 2911 [41, 71]
New numbers: 7141 4171
Divisors of 4171 [43, 97]
New numbers: 9743 4397
Divisors of 7141 [37, 193]
New numbers: 19337 37193
4397 is Not Semi Prime
9743 is Not Semi Prime
Divisors of 37193 [13, 2861]
New numbers: 286113 132861
Divisors of 19337 [61, 317]
New numbers: 31761 61317
132861 is Not Semi Prime
286113 is Not Semi Prime
61317 is Not Semi Prime
31761 is Not Semi Prime

[mnh001]

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.

Error:
Traceback (most recent call last):
  File "c:\Python38-32\Scripts\P1015b.py", line 16, in <module>
    a = divisors(x)
  File "c:\Python38-32\Scripts\P1015b.py", line 10, in divisors
    new_numbers(div)
NameError: name 'new_numbers' is not defined

I take it there's more to it than what you showed?

[DPaul]

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

[bowlofred]

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.

[mnh001]

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.