-5

I noticed a strange phenomenon while examining prime numbers. Here it is:

We'll say num = number
If num's sum of digits is 4 and num is not even, num is prime.
Can somebody explain to me why this happens?

Here is a Node.js program for proof: http://pastebin.com/a35uXxKk

EDIT: Output:

13 (Is prime as well) 31 (Is prime as well) 103 (Is prime as well) 211 (Is prime as well) 301 (If you see this, something is wrong) 1003 (If you see this, something is wrong) 1021 (Is prime as well) 1201 (Is prime as well) 2011 (Is prime as well) 3001 (Is prime as well)

This means numbers with (If you see this, something is wrong) are exceptions. Can people help me make a rule for ruling out these exceptions?

EDIT 2:

Most of the exceptions are divisible by 11. Taking out those seemed to eliminate most exceptions.

EDIT 3:

It seems if a number got ruled out by my previous revisions, any of the digit rearrangements will not work either.

Comment why if you downvote so I can improve

TigerGold
  • 339
  • 2
    $1111 = 11\cdot 101$ – Ant May 07 '16 at 22:34
  • I don't know, my program says that is prime as well – TigerGold May 07 '16 at 22:34
  • But as far as I know, that is the only exception – TigerGold May 07 '16 at 22:35
  • 4
    Can I mention $110011=11\cdot10001$? – bof May 07 '16 at 22:37
  • 4
    Another exception is $121 = 11^2$. – Zoe H May 07 '16 at 22:38
  • Hmmm, never noticed these exceptions. – TigerGold May 07 '16 at 22:39
  • The claim you are making is certainly not true (with or without taking into account the special case for number divisible by 11) – Mariano Suárez-Álvarez May 07 '16 at 22:56
  • @MarianoSuárez-Alvarez I know, I have revised my question. – TigerGold May 07 '16 at 22:57
  • If you have a clear question, please post it. This stream of consciousness does not work here; pause and reflect on the situation, play around with the numbers on your own, clarify some issues, then come back with a clear, defined question – Ant May 07 '16 at 23:01
  • OK, I though I had it. – TigerGold May 07 '16 at 23:02
  • sum of num=4 just means that the number can be written as $3k+4$ (with k odd as you remove even numbers). such a number is not a multiple of 2 or 3 (which eliminates a lot of non-primes), but can perfectly be a multiple of some bigger prime. haven't made the maths, but I'm confident that the number of such primes goes down as the numbers grow larger. – imj May 07 '16 at 23:04
  • @imj interesting.. How to prove that the numbers must be in that form? – Ant May 07 '16 at 23:09
  • https://en.wikipedia.org/wiki/Divisibility_rule#Divisibility_by_3_or_9 – imj May 07 '16 at 23:10
  • 3
    $11000000000000010001$ is an example of a odd number with digit sum 4, not divisible by $11$ and not prime. – Henrik supports the community May 07 '16 at 23:26
  • @Ant If you have a number $n$ with a sum of digits of $4$, then you can subtract one of the digits by $1$ to get a number with a sum of digits of $3$, which is a multiple of $3$, or $3l$. However, subtracting one of the digits by $1$ is basically the same as subtracting by a power of $10$, so we have $$n-10^m=3l$$ However $10 \equiv 1 \pmod 3$, so $10^m \equiv 1 \pmod 3$. Since the difference of $n$ and $10^m$ is a power of $3$, this gives us $n \equiv 1 \pmod 3$, so $n \equiv 4 \pmod 3$, so $$n=3k+4$$ – Noble Mushtak May 07 '16 at 23:44

2 Answers2

3

This is not true. Your program is, unfortunately, written incorrectly:

number % i === 0 && !i === number && !i == 1

!i === number is not correct logic because you're taking the negation of i, which makes no sense in this scenario. You need to use the !== operator when checking if two values are unequal, so it should be this:

number % i === 0 && i !== number && i !== 1

Another valid solution is to put the == expression in parentheses so you take the negation of the whole Boolean expression:

number % i === 0 && !(i === number) && !(i === 1)
Noble Mushtak
  • 18,402
  • 28
  • 44
3

You've asked for an explanation for what you saw, and even though it isn't correct, some things can be said about why counterexamples aren't smaller than they are.

By requiring the numbers to be odd, you exclude multiples of $2$.

As the iterated digital sum of a number equals the number's residue modulo $9$, a neccessary (but far from sufficient) condition for that requirement to be fulfilled, is that the number is of the form $9k+4$, that shows us that you've ruled out all multiples of $3$.

As the odd multiples of $5$ end with a $5$, they can't have $4$ as the sum of their digits, which means you've ruled out multiples of $5$.

So you've ruled out a lot of non-primes.

In general only a few numbers between $49$ (the square of the lowest prime you haven't ruled out and $999$ have $4$ as the sum of their digits and by coincidence (?, arguments can possibly be found, and I haven't actually checked) none of them are prime. Which explains why you didn't see any counterexamples, and they start appearing not long after $1000$ (it has been mentioned may times in the comments that $1111=11\cdot 101$ is a counter example).

Then you can rule out multiples of $11$ (your edit) and have a rule that holds a little longer, but counterexamples will still exist (I've given one in the comments, where $17$ is the smallest prime factor - I generated that by "randomly" inserting $0$'s to $1111$, so it's unlikely to be the smallest).

Henrik supports the community
  • 6,831