Question

30 has a bunch of divisors. If you break it up into any 2 divisors such as 1+30=31, 2+15=17, 3+10=13, 5+6=11 all of these numbers are prime.

Are there infinitely many numbers like 30?

Answer 1

Ok, so it's asking if you did the same to another number, would you only get prime numbers.

Answer 2

first the number need to be even xD

Answer 3

Yeah it has to be even. Also it has to be square free. :P

Answer 4

tots!

*acting like i would conclude something brilliant*

Answer 5

Beats me if there are infinitely many though. I have a few more tricks up my sleeve but not enough to really get anywhere

Answer 6

Choose any number you want and we'll try that.

Answer 7

I'm just messing around and slightly sleepy so idk what I'm doing really tbh just having fun lol

Answer 8

Well do you want an answer? It is a really simple problem.

Answer 9

i think this is been directly related to perfect numbers

Answer 10

Here's the "More official version"

Are there infinitely many \(n\) such that for all divisors \(d\)
\[\left( d + \frac{n}{d}\right) \text{ is prime? }\]

Answer 11

Say you choose 15 well we would need to find what two numbers multiply which we can see is 3 * 5. This would actually be 3 + 5 in this case. Now we add then tell me if the number you get after adding is prime.

Answer 12

all I was able to figure out is if n is not square free then there's some \(d^2|n\) so then:

\[d + \frac{n}{d} = d(1 + \frac{n}{d^2} )\]
so this is not prime and it fails.

The other thing is that n is a divisor of itself so it is one less than some prime p:

\[1+\frac{n}{1} = p\]

and the final thing is since we know n is even we can write it as \(n=2m\) and similarly there is some prime q:
\[2+m = q\]

so we require that all numbers that satisfy this also means that:

\[3+p = 2*q\]

So if this only happens finitely many times we know there can only be finitely many of thes numbers but idk past this haha. I'm sure there are more cute tricks like this waiting to be found.

Answer 13

Well as you know 5 + 3 is 8 and this number isn't prime so our answer would be no.

Answer 14

@jchick This would be one number that doesn't work but that doesn't mean there aren't infinitely many other numbers that work :X

Answer 15

I think you're onto something with this perfect numbers stuff ikram cause \(n+1\) being prime is pretty similar to \(2^k-1\) being prime..!

Answer 16

wait maybe I'm thinking backwards damn

Answer 17

i'll think about these stuff till evening!
\(\sigma(d)+\sigma(\frac {n}{d})=...\)

Answer 18

yeah I keep trying to think of how to write something like you have there hmmm it is like begging to be inside something like this I feel: \(\sum_{d|n} \cdots\)

Answer 19

I noticed that because divisors come in pairs that each number has only half as many primes as it does ways of getting them so the total number of primes a number will have is:

\[2^{\Omega(n)-1}\]

So for instance, \(\Omega(30)= 3\) so there are half as many as \(2^{3}\) there are only 4.

hmmm some other possibly useful bits and pieces:

\[\mu(n) \ne 0\] and maybe \(p_k \#\) is a good candidate for looking for answers.

Answer 20

I think proving infinitely many solutions exist for \(3+p = 2*q\)
takes more or less same effort as proving twin prime conjective

Answer 21

you want to find prime pairs (p, (p+3)/2)

Answer 22

Well I was thinking more along the lines that it might be possible to prove that there are only finitely many solutions to that equation. But yeah I agree

Answer 23

(p+3)/2 is a prime when p is :

[3,7,11,19,23,31,43,59,71,79,83,103,131,139,163,191,199,211,223,251,271,311,331,359,379,383,419,443,463,479,499,523,563,619,631,659,691,743,839,859,863,883,911,919,971]

Answer 24

looks there is no natural upper limit..

Answer 25

Yeah there are quite a few, I tried throwing Dirichlet's theorem at it by looking at this relation between these two primes in mod 6 bu wasn't able to get anywhere since I suspect the same hmmm

Answer 26

\(\sigma(n)\),\(\sigma\left(\frac{n}{d}\right)\) and \(\sum_{d|n}\) all reminds me of Mobius inversion. \(2^k-1\) reminds me of Mersenne primes.

Answer 27

I of course have no idea what I am saying since I don't know any number theory.

Answer 28

Yeah funny you should say that, ikram and I were thinking about this too but I just don't know how to get it to work out.

On the other hand, like for 30 we can write:

\[\sigma(30) =(1+30) + (2+15) + (3+10) + (5+ 6) = 31+17+13+11\]

and from what I was looking at earlier because 30 has 3 unique prime factors it has \(2^{3-1} = 4\) primes... I guess in other words these numbers have their sum of divisors function equal to a specific sum of primes.

\[\sigma(n) = \sum_{k=1}^{2^{\omega(n) -1}} p_k\]

Also \(\mu(n) \ne 0\) because it's square free, but this is as far as I've gotten. Perfect numbers and Mersenne primes are pretty closely related with all of this it feels like so this is really interesting to me right now.

Answer 29

If you haven't seen this it's pretty cool imo

https://primes.utm.edu/notes/proofs/EvenPerfect.html

every even perfect number is a power of 2 times a Mersenne prime and you can prove this through the \(\sigma(n)\) function.

Answer 30

Since \(\sigma = N \star u = \varphi \star \tau\) I'm playing around with their Mobius inversions now maybe something cool will fall out. Probably not though lol.

Answer 31

How would you express 30+1, 6+5 and 3+10 using number theoretic functions?

Answer 32

Well essentially that's what I did, there are tons of other ways we could do it too though

Answer 33

In particular, how can you express the condition that \(
d+\dfrac{n}{d}
\) is prime for all \(d|n\)?

Answer 34

Hmmm that's a good way of putting it but I'm not sure.

What I did was since \(d + \frac{n}{d}\) is supposed to be a prime, I just sorta asserted it as the form when writing that last thing. But I didn't prove anything.

It could be though while carrying around this general form of the numbers that do satisfy this condition that it reveals some nice way to prove it is true for infinitely many things though?

Answer 35

\(\sum\limits_{d\mid n} \gcd(d,\dfrac{n}{d})=n\)

is satisfied by all squarefree integers \(n\) is it ?

Answer 36

yeah, \(p\) is present in either \(d\) or \(n/d\), not both

Answer 37

Is it? I don't know, I only know n is square free because if it had some square divisor \(d^2 |n\) then one of the terms is not a prime

\[(d+\frac{n}{d}) = d^2 ( 1 + \frac{n}{d^2}) \ne p\]

Answer 38

**
\(\sum\limits_{d\mid n} \gcd(d,\dfrac{n}{d})=\tau(n)\)

Answer 39

Ahhh ok I was just about to remark I have not seen that old one and was wondering about some relationship to this:

\[\sum_{d|n} \varphi(d) = n\]

Answer 40

Interesting I really like this, i have not seen this before. Are there other such squarefree identities like this or is this sorta like just some random thing

Answer 41

its a trivial one... i have cooked it up from your previous reply..

Answer 42

do you have a list of other solutions like 30 ?

Answer 43

I don't off hand but I can genreate some because I really got this from https://projecteuler.net/problem=357

However what I'm doing is like a generalization on this, I already solved the problem the other night.

Answer 44

\[
\omega\left(\prod_{d|n}\left(d+\frac{n}{d}\right)\right)=\sum_{d|n}\omega\left(d+\frac{n}{d}\right)\]
I genuinely have no idea what I am writing now. It reminds me of logarithm though.

Answer 45

yeah that seems true in general
\(\omega(ab) = \omega(a)+\omega(b)\)

Answer 46

for squarefree \(n\), that also equals

\[\omega\left(\prod_{d|n}\left(d+\frac{n}{d}\right)\right)=\sum_{d|n}\omega\left(d+\frac{n}{d}\right)=\tau(n)\]

Answer 47

because \(\omega(d+\dfrac{n}{d})=\omega(p)=1\)

Answer 48

im gonna generate the list quick @Kainui ..

Answer 49

**
for solutions \(n\) of present problem

\[\omega\left(\prod_{d|n}\left(d+\frac{n}{d}\right)\right)=\sum_{d|n}\omega\left(d+\frac{n}{d}\right)=\tau(n)\]

Answer 50

Shouldn't that be \(\tau(n)-1\) because 1 is always a divisor and \(\omega(n)\) does not count 1?

Answer 51

when \(d = 1\), the term in the sum is :
\[\omega(1+\dfrac{n}{1})=\omega(1+n)\]

right ?

Answer 52

\(\sum\limits_{d\mid n} f(d)\)

when we expand this expression, we get exactly \(\tau(n)\) terms no matter what \(f(d)\) is

Answer 53

As they say in computer science, there are two things that are hard in computer science, naming things, cache invalidation and off-by-one errors.

Answer 54

\(\omega(n)\) is a bit tough function
its not multiplicative, so we cannot use most of number theory tricks..

Answer 55

here are the integers below 1000 such that d+n/d is always a prime :

[2,6,10,22,30,42,58,70,78,82,102,130,190,210,310,330,358,382,442,462,478,562,658,742,838,862,970]

Answer 56

Looks there are many solutions of form \(2p\)

Answer 57

solutions of form \(2p\) :

[6,10,22,58,82,358,382,478,562,838,862]

Answer 58

Wow, these connect "twinprimes" and "sophie germain primes"

For \(2p\) to be a solution, the necessary and sufficient conditions are :
\(2p+1\) must be a prime
\(p+2\) must be a prime

Answer 59

your problem is more mysterious than it appears to be!

Answer 60

Woah I had to do something and left and now I'm wishing I hadn't! I missed quite a bit I gotta catch up sorry!

Answer 61

Woah. I've heard of Sophie Germain primes and I think Cunningham Chains, but I guess now here's my sign to read into them a little more to see what's going on. Very cool observation about the logarithm-ishness of the \(\omega\). :D

Answer 62

I really like how there's this parallel of unrelated facts.

Because the divisors are square free:
\[\sum_{d|n} \gcd(d , \tfrac{n}{d}) = \tau(n)\]
Because these numbers are primes:
\[\sum_{d|n} \omega(d + \tfrac{n}{d}) = \tau(n)\]

Answer 63

I'm looking at some way to combine these with this convolution perhaps to get some interesting things out.

\[\sigma(n) = \sum_{d|n} \tau(d) \varphi(\tfrac{n}{d}) = \sum_{k=1}^{2^{\omega(n)-1}} p_k = \sum_{d|n} d = \sum_{d|n} \tfrac{n}{d} \]

Answer 64

What is the Mobius inversion of \(\sum_{d|n}\omega\left(d+\frac{n}{d}\right)\)?

Answer 65

Does it even make sense to ask for Möbius inversion of \(\sum_{d|n}\omega\left(d+\frac{n}{d}\right)\)? I only noticed the extreme similarity between \(g(n)=\sum_{d|n}f(d)\) and the sum .

Answer 66

Since it's square free I realized we can split up a term of

\[\tau(d) \varphi(\tfrac{n}{d}) = \prod_{primes} \varphi(p^a)\tau(p^b)\]
with every combination of \(a+b=1\), in other words there are really only two terms contributing to a factor:

\[\tau(1)\varphi(p) = p-1\]\[\tau(p) \varphi(1) = 2\]

and these are all multiplicative and we can sorta scoop these together and I'm still working through the detail.

I don't think that thing @thomas5267 has a mobius inversion because the term \(\omega( d + \tfrac{n}{d}) \) depends on two variables and not just 1.

Answer 67

The only thing I knew about Sophie Germain primes is that it is common used in cryptography because something related to them are particularly hard to factor. This is getting really interesting.

Answer 68

Interesting fact from http://primes.utm.edu/glossary/xpage/SophieGermainPrime.html

if \(p \equiv 3 \mod 4\) and \(p>3\) then the prime \(2p+1\) divides the Mersenne number \(M_p\).

Hmm there are so many weird seemingly unrelated facts in number theory just sprinkled all over the place. I really wish there was some good way to connect them all in some simple way that doesn't feel like memorization lol.

Answer 69

It suddenly dawned on me that this is getting ridiculous. If there is an infinite amount of solution and the proportion of solution in the form of 2p is larger than 0, then we will have proven the twin prime conjecture based on the necessary and sufficient condition of solutions in the form of 2p provided by ganeshie8...

Answer 70

oi wait if that's true let me scroll up now that I know what a Sophie Germain prime is I need to read the content of his post again.

Answer 71

Ahh ok no, what he's saying is only partly a subset of the thing I want to prove. Proving what I am looking for will not imply the twin primes conjecture

Answer 72

He's saying if n=2p then in order for it to be a solution, 2p+1 and p+2 are prime.

However n=30 is none of these things and works.

Answer 73

this is actually a really cool observation @ganeshie8 now that I understand what you're saying. It leaves us with some interesting routes to proving this in a world where it's proven that there are infinitely many twin primes and infinitely many sophie germain primes of certain related forms.

Even if we assume there are infinitely many of both we still need to prove that they would be related so closely like this. Oh well. This is only one special case of what I'm interested in so either this is a bad sign or a good sign I'm not sure lol

Answer 74

Is this correct for the n we are looking for?
\[
\frac{1}{2}\sum_{d|n}\tau\left(d+\frac{n}{d}\right)=\tau\left(\prod_{d|n}\left(d+\frac{n}{d}\right)\right)
\]

Answer 75

The problem is if there is an infinite amount of solutions in the form of 2p we would have proven twin prime conjecture. So either this does not have an infinite amount of solution or the proportion of solution in the form of 2p is 0.

Answer 76

It might be that there is some simple way to prove that numbers that are the products of consecutive primes (of which there are infinitely many) always exist so that would prove there are infinitely many without ever worrying about whether twin primes is true or false, there's not really any conflict here.

That thing you wrote I think that's correct yeah, looks interesting

Answer 77

Wait I think it's off by some factors of 2 now that I'm thinking about it more

Answer 78

What if there is only a finite amount of solution in the form of 2p? Would we have disproved the twin prime conjecture?

Answer 79

nope because our answers that are of the form 2p are both twin primes and sophie germain primes. So there could be infinitely many twin primes and infinitely many sophie germain primes and only finitely many primes that are both twin primes AND sophie germain primes simultaneously.

Answer 80

Good. So if we have a finite amount of solution in the form of 2p we won't be screwed by the twin-prime conjecture.

I have to sleep now. Good night.

Answer 81

Alright later, thanks for playing haha

Answer 82

\[\frac{1}{2}\sum_{d|n}\tau\left(d+\frac{n}{d}\right)=\tau\left(\prod_{d|n}\left(d+\frac{n}{d}\right)\right)\]
It is certainly incorrect. My idea is that the left hand side is the number of "divisors sum" and the right hand is the number of divisors of product of divisors sums (read as: number of (divisors of (product of divisors sums)) ). I thought for primes \(p_1\) and \(p_2\), \(\tau(p_1p_2)=\tau(p_1)\tau(p_2)=4\) which is clearly not true.

Answer 83

\(\tau\) is multiplciatie
so \(\tau(p_1p_2) = \tau(p_1)\tau(p_2)\) is certainly true when \(p_1\ne p_2\)

Answer 84

Yeah the right hand side is really cool and clever it's a product of 2s and on the left it's a sum of 2s so it doesn't quite match up.