Question about the Divisor Function/Sums and Project Euler

In summary, the conversation revolves around a question about the Divisor Function and its relation to algebraic functions. The individual is looking for a way to solve for solutions by hand, but it seems that this may not be possible without advanced knowledge in analytic number theory and real analysis. Techniques used for finding perfect numbers and mersenne primes may also apply to finding solutions for different values of a and b.
  • #1
Delta31415
90
8
So I am kind of lost... I don't really know how to ask this.
Project Euler is a website that hosts multiple programming contests and I am interested in this problem
https://projecteuler.net/problem=608
but my question isn't truly about this problem but a more solution.

I know that the Divisor Function is
[itex]{\displaystyle \sigma _{x}(n)=\sum _{d\mid n}d^{x}\,\!}[/itex]
my question is can I set the Divisor function equal to an algebraic function of value x and solve for the solutions
for example:

[itex]{\displaystyle \sigma _{x}(n)=\sum _{d\mid n}d^{x}\,\!} = (x^2+7)\ or\ (x+9)\ or\ even\ ln(x)[/itex]
p.s I know that I can do this using programming and I have but I would like to be able to do it by hand as well.
I have recently been reading some elementary number theory textbooks but all they do is talk about primes and things such as the division algorithm, the divisor function isn't even mentioned.

Thanks for the help and I am sorry for being so confusing.
Edit: finally fixed the Latex
 
Last edited:
Mathematics news on Phys.org
  • #2
Number theory seems to be concerned with keeping x a fixed integer and varying n. Varying x while keeping n fixed is more a real analysis question. Even for
something as simple as [itex] \sigma_x(2) = ax + b [/itex] you won't be able to get an answer using elementary functions for most values of a and b.. You could look up the lambert W function
https://en.wikipedia.org/wiki/Lambert_W_function#Solutions_of_equations (see example 1)
 
  • Like
Likes Delta31415
  • #3
willem2 said:
Number theory seems to be concerned with keeping x a fixed integer and varying n. Varying x while keeping n fixed is more a real analysis question. Even for
something as simple as [itex] \sigma_x(2) = ax + b [/itex] you won't be able to get an answer using elementary functions for most values of a and b.. You could look up the lambert W function
https://en.wikipedia.org/wiki/Lambert_W_function#Solutions_of_equations (see example 1)

so I have been reading the wrong textbooks and should look into analytic number theory and real analysis and thxs for the link

Edit: I have looked at the link and most of it involves exponentials, so my question should I try to convert the divisor function into an integral or is this even possible
 
  • #4
I just noticed a big mistake that I made and I cannot edit it now >_>

The X in the divisor function should be 1 as I am finding the sum of proper divisors and the algebraic variable should be n instead of x as x has a value of 1 in this case
[itex]{\displaystyle \sigma _{1}(n)=\sum _{d\mid n}d^{1}\,\!} = an+b[/itex]

which would make it a more of a number theory question
 
  • #5
Delta31415 said:
[itex]{\displaystyle \sigma _{1}(n)=\sum _{d\mid n}d^{1}\,\!} = an+b[/itex]

which would make it a more of a number theory question
Yes. If a =2 and b=0 these are the perfect numbers. If a>2 and b is 0, mutltiperfect numbers.
You probably need a different procedure for all different values of a and b. For example σ(n) = n+1 is valid if n is prime, σ(n) = n+2 is impossible, etc.
It's unknown wether there are odd perfect numbers, and for even perfect numbers you need to find mersenne primes. Techniques to find these or prove them impossible would probably apply for other values of a and b.
 
  • Like
Likes Delta31415

1. What is the Divisor Function?

The Divisor Function, denoted by σ(n), is a mathematical function that calculates the sum of all positive divisors of a given positive integer n. It is also known as the sum-of-divisors function.

2. How is the Divisor Function used in Project Euler problems?

The Divisor Function is commonly used in Project Euler problems as it helps in finding the factors of a number, which is often a crucial step in solving the problem. It can also be used to check whether a number is a perfect number or not.

3. What are the properties of the Divisor Function?

The Divisor Function has several important properties, such as:

  • σ(1) = 1
  • σ(p) = p + 1, where p is a prime number
  • σ(p^k) = (p^(k+1) - 1)/(p - 1), where p is a prime number and k is a positive integer
  • If n = p1^a1 * p2^a2 * ... * pk^ak, then σ(n) = σ(p1^a1) * σ(p2^a2) * ... * σ(pk^ak)

4. Can the Divisor Function be calculated efficiently for large numbers?

The Divisor Function can be calculated efficiently for large numbers using various algorithms, such as the Sieve of Eratosthenes, which can find all the divisors of a number in O(nlog(n)) time. There are also other more advanced algorithms that can calculate the Divisor Function in even faster time.

5. Are there any other applications of the Divisor Function?

Aside from its use in Project Euler problems, the Divisor Function also has applications in number theory, such as in the study of perfect numbers, amicable numbers, and sociable numbers. It is also used in cryptography, specifically in the RSA algorithm, to generate the public and private keys.

Similar threads

Replies
1
Views
2K
Replies
4
Views
419
  • STEM Academic Advising
Replies
10
Views
1K
  • Engineering and Comp Sci Homework Help
3
Replies
80
Views
8K
Replies
4
Views
935
Replies
4
Views
3K
Replies
7
Views
2K
Replies
2
Views
1K
  • General Math
Replies
2
Views
1K
Back
Top