Ryan's Poly-Sum-Deficiency?

Computer Science Level 4

The aliquot sum $s(n)$ of a natural number $n$ is the sum of its proper divisors; in other words, the sum of its divisors subtracted by $n$ . For example, $s(6) = 1+2+3 = 6$ .

A natural number $n$ is deficient if $s(n) < n$ . For example, $6$ is not deficient since $s(6) = 6 \ge 6$ , but $8$ is deficient since $s(8) = 7 < 8$ .

A natural number $n$ is triangular if there exists a natural number $m$ such that $n = \frac{m(m+1)}{2}$ . Note that $0$ is not considered triangular.

A natural number $n$ is a 3-Ryan number if both $n$ and $s(n)$ are distinct triangular numbers. For example, $3$ is a 3-Ryan number since $3$ and $s(3) = 1$ are distinct triangular numbers, but $6$ isn't since $6$ and $s(6) = 6$ are not distinct, $10$ isn't since $s(10) = 8$ is not a triangular number, and $4$ isn't since $4$ is not a triangular number.

Determine the 7th smallest deficient 3-Ryan number.

The answer is 2476425.

2 solutions

Aareyan Manzoor
Aug 31, 2015

took around 5-10 mins python2:

def s(n):
     k = 1
     for i in range(2,n/2+1):
         if(n%i==0):
             k += i
     return(k)
ryanlist = []
i = 3
n = 3
while(len(ryanlist)<7):
    if(s(i)<i):
         if((-1+(1+8*s(i))**(0.5))/2.0%1==0):
             ryanlist.append(i)  
    i += n
    n += 1
print(ryanlist[6])

i made it as less time consuming as possible after several attempt in terminal. divisor of a number <= number/2. used in line 5. in line 12 (-1+(1+8 s(i)) *(0.5))/2.0 by quadratic formula means that s(i) is a triangular number.n need if i triangular number because there is already i+=n,n+=1 meaning only triangular 'i's are inputted.this decreases time from which otherwise could've been 2-10hrs to 5-10mins.

Aareyan Manzoor - 5 years, 9 months ago

hmmm, 5min is way too long for the number asked, especially when it can be solved under a second, You might want to polish up on the sum of divisors function..

Beakal Tiliksew - 5 years, 9 months ago

how,sir? i halved n. any easier way?

Aareyan Manzoor - 5 years, 9 months ago

@Aareyan Manzoor – The idea is related to the divisor function. This will be of help.

It doesn't have to be easier to be more efficient, in fact this will be harder to implement, but the trade off is well worth it.

Beakal Tiliksew - 5 years, 9 months ago

@Aareyan Manzoor – Perhaps it would be more efficient if when $n \mod{i} = 0$ , you add $i$ and $\frac{n}{i}$ to the sum?

Ryan Tamburrino - 5 years, 9 months ago

@Ryan Tamburrino – Yeah, and it could be made way more efficient by prime factorizing the number using it for sum of divisors.

Beakal Tiliksew - 5 years, 9 months ago

Ryan Tamburrino
Aug 12, 2015

Here is my solution, in Python 3.4, I believe. Looks a little long to me. But, alas, I am relatively new to programming and all, so give me a break:

#Objective: find the 7th smallest number n such that s(n), the aliquot sum, and n are distinct triangular numbers.

import math

#Implementation of the aliquot function, which sums the proper factors of any positive integer.
def aliquot(n):
    factors = []
    prop = 1
    while (prop < n):
        if (n % prop == 0):
            factors.append(prop)
        prop += 1
    return (sum(factors))

#Returns the nth triangular number.
def tri(n):
    return (int(n*(n+1)/2))

#Tests the triangularity of some positive integer n.
def isTri(n):
    f = 1
    while (f < math.ceil(math.sqrt(2*n))):
        if (f == (2*n/f)-1):
            return True
        f += 1
    return False

#Generating a list of triangular numbers.
triList = []
index1 = 1
#Try to keep this bound at or below 2,500. After that, runtime really drags.
#Perhaps someone can offer a better method!
while (index1 <= 2300):
    triList.append(tri(index1))
    index1 += 1

#Initializing alpha, as a sliding index for triList.
#Initializing deficiency, to count the number of deficients n's satisfiying the conditions.
alpha = 0
deficiency = 0

#Test.
while (alpha < len(triList)):
    currentTri = triList[alpha]
    if (isTri(aliquot(currentTri)) and (aliquot(currentTri) != currentTri)):
        if(aliquot(currentTri) < currentTri):
            deficiency += 1
            if (deficiency == 7):
                print("{currentTri} is the 7th deficient 3-Ryan number.".format(currentTri=currentTri)
    alpha += 1

Ryan's Poly-Sum-Deficiency?

The answer is 2476425.

2 solutions

0 pending reports