17

first of all, I'm no mathematician at all. I was just playing with prime numbers and ended up with this list:

2 = 2¹
3 = 3¹
5 = 5¹
7 = 3¹ + 2²
11 = 2¹ + 3²
13 = 13¹
17 = 5¹ + 2² + 2³
19 = 2¹ + 3² + 2³
23 = 11¹ + 2² + 2³
29 = 17¹ + 2² + 2³
31 = 19¹ + 2² + 2³
37 = 37¹
41 = 5¹ + 3² + 3³
43 = 7¹ + 3² + 3³
47 = 11¹ + 3² + 3³
53 = 17¹ + 3² + 3³
59 = 23¹ + 3² + 3³
61 = 61¹
67 = 7¹ + 2² + 2³ + 24 + 25
71 = 67¹ + 2²
73 = 61¹ + 2² + 2³
79 = 3¹ + 7² + 3³
83 = 79¹ + 2²
89 = 13¹ + 7² + 3³
97 = 13¹ + 3² + 3³ + 24 + 25
101 = 97¹ + 22
103 = 11¹ + 72 + 33 + 24
107 = 103¹ + 22
109 = 17¹ + 72 + 33 + 24

Edit2: As pointed out by @Charles, 29, 67 and 97 aren't annoying.

I was just playing by trying to write the primes following this form

a1 + b2 + c3 ...

(just one rule, there must be all the exponents, or else the number must be written by itself. So, I can't have a number written in the form a1 + b3 + c4)

Edit: There are actually two rules, I forgot to say that a, b, c... must be primes.

Some of the primes, the bold ones, can only be written with exponent 1. I called then annoying primes, in lack of a better name.

Is it some property of these primes? Is there a formula to express this?

Alexandre Paloschi Horta
  • 173
  • 5
  • Here the MathJax tutorial for future reference – gen-ℤ ready to perish Oct 24 '17 at 04:51
  • Seems unlikely to bear interesting fruit. But every Mersenne prime greater than $3$ can be written as $2^{p}-1=3^1+2^2+2^3+\cdots +2^{p-1}$. – Thomas Andrews Oct 24 '17 at 04:53
  • 2
    I suspect that primes are not special here. If you tried the composites I think you would find the same density of annoying numbers. Just guessing. – Ross Millikan Oct 24 '17 at 05:23
  • @RossMillikan They are at least special in that the RHS must be powers of primes to make this interresting... – skyking Oct 24 '17 at 05:48
  • Any prime like $P_1$ can be written as the sum of powers of a smaller prime like $P_2$ and a constant like c. For example$17=2^4+1$.So a prime like 109,for example, can be written as:$109=2^4 +1 + 2^3 +1 +2^1 +1 +2^4=2 . 2^4 + 2^3 + 2^2 + 1$ .This relates to old question of Euler : Is the number of primes from polynomial $x^2-1$ or generally $ax^2+b x + c$ infinity? Your experience shows that the answer may be yes. – sirous Oct 24 '17 at 09:55
  • @skyking: I meant that I didn't think the numbers on the left are prime is important. – Ross Millikan Oct 24 '17 at 14:33
  • @skyking What is RHS? (I told you, no mathematician, hehe.) – Alexandre Paloschi Horta Oct 25 '17 at 00:18
  • @AlexandrePaloschiHorta Right hand side. –  Oct 25 '17 at 00:22
  • Hmm, the underlying question, Can $n$ be written in the form $p_1^1+p_2^2+p_3^3+\cdots$ where the $p_i$'s are primes?, in in $NP$: the answer Yes is easily verified if you know the primes, but the answer No looks computationally difficult to verify. The name "annoying" may be justified! – Barry Cipra Oct 25 '17 at 01:29
  • @BarryCipra Finding the largest exponent may be hard, but I suspect your problem is in P. This might require some sort of Goldbach/Vinogradov type work to prove. – Charles Oct 25 '17 at 07:01

1 Answers1

7

I can only find 6 annoying primes: 2, 3, 5, 13, 37, and 61.

You gave these and three other examples, but they don’t hold: $$29 = 17 + 2^2 + 2^3$$ $$67 = 7 + 2^2 + 2^3 + 2^4 + 2^5$$ $$97 = 13 + 3^2 + 3^3 + 2^4 + 2^5$$

By general density arguments one would expect:

Conjecture: There are only finitely many annoying primes.

I pose this problem which would strengthen my conjecture:

Open problem: Are there finitely many numbers which cannot be expressed with greatest exponent 2, 3, 4, or 5?

Sadly I do not have a computer here to check, perhaps someone else will do so and report back.

Charles
  • 32,122
  • Corrected, thanks for pointing out. About your open problem, I leave it for you folks. Guess I'll be just observing for now, hehe. – Alexandre Paloschi Horta Oct 25 '17 at 11:10
  • @AlexandrePaloschiHorta, I would encourage you to continue playing with the problem, e.g., see if you can find some more annoying primes. Congratulations on coming up with a nice problem. – Barry Cipra Oct 25 '17 at 11:53
  • @AlexandrePaloschiHorta It’s a nice problem, thanks for bringing it up. – Charles Oct 25 '17 at 13:04
  • Except from ${2,3,5,13,37,61}$ no primenumber less than $20,000$ is annoying. And these primes can be expressed with greatest exponent $2,3,4$ or $5$. – Lehs Oct 25 '17 at 20:30
  • WTF?!?!? Hey, @BarryCipra, were you trying to lure me into a quest like that? 20.000!?!?!? :D – Alexandre Paloschi Horta Oct 25 '17 at 22:59
  • @Lehs How did you come to that conclusion? – Alexandre Paloschi Horta Oct 25 '17 at 23:00
  • @AlexandrePaloschiHorta, as Ross Millikan suggested in comments, you might try looking for (small) composite numbers that cannot be written as a sum of the first few powers of primes. I find that $4$, $8$, and $10$ are "annoying" while $6=2^1+2^2$ and $9=5^1+2^2$ are not. – Barry Cipra Oct 25 '17 at 23:25
  • Nice! Will do that, for sure! At least I'll have some fun before 20.000. – Alexandre Paloschi Horta Oct 26 '17 at 00:12
  • @AlexandrePaloschiHorta: I made a program that tested. Since I like your problem I will make an other program, working different, to make a double check (and to see if it works more efficient). I've tested up to $50,000$ right now and still $61$ is the largest annoying prime number found. – Lehs Oct 26 '17 at 06:22
  • See https://math.stackexchange.com/questions/2490483/the-set-of-numbers-of-the-form-q-1q-22q-33q-44q-55-where-all-q-k-are?noredirect=1#comment5145051_2490483 – Lehs Oct 26 '17 at 11:35
  • @Lehs In the conjecture you posted, why did you choose to limit the number of exponents to five? (Asking it here so I don't spoil the math discussion there.) – Alexandre Paloschi Horta Oct 30 '17 at 02:19
  • @AlexandrePaloschiHorta Probably because I did in my answer. The reason I stopped at 5 was I was fairly sure I didn’t need to go higher. Probably if I had computing tools I would have been comfortable going lower. – Charles Oct 30 '17 at 02:48
  • @AlexandrePaloschiHorta: yes, it was because of the conjectures of Charles. Probably even three would have been enough. Which is even more interesting. – Lehs Oct 30 '17 at 04:41
  • @Lehs Agreed! And good work! – Charles Oct 30 '17 at 04:57
  • @Lehs where are you up to, now? hahah – Mr Pie Jan 25 '18 at 05:02
  • @user477343: I'm looking at https://mathoverflow.net/questions/282904/about-prime-numbers-and-the-sums-of-three-distinct-cubes – Lehs Jan 25 '18 at 05:50