3

I have tested all the primes up to 50,000,000 and did not find a single prime which satisfies the condition "sum of digits of prime number written in base7 divides by 3". E.g.

  • 13 (Base10) = 16 (Base7) --> 7 (sum of digits in base 7)
  • 1021 (Base10) = 2656 (Base7) --> 19
  • 823541 (Base10) = 6666665 (Base7) --> 41
  • 46941953 (Base10) = 1110000002 (Base7) --> 5

Here you can see the distribution of sums in base 7:

http://s12.postimg.org/lcf3tntzx/prime_sum_in_base7_distribution.png

  • COUNT(*) - the number of occurrences
  • SUM7 - sum of digits in base7
  • MIN(PRIME) - minimal prime in base10
  • MAX(PRIME) - maximal prime in base10

As you can see sum7 of 9, 15, 21, 27, 33 are missing in the list, though other valid sums are widely represented. By 'valid sum' I mean that sum must be odd, because of "In an odd base, a number is odd if and only if it has an odd number of odd digits."

So what is the least prime whose sum of digits written in base7 divide by 3? Or is it possible to prove that all primes have such a feature?

Buchas
  • 83
  • "Tested all primes up to 50 million". That's funny, I just tested all primes up to $3$ and found one whose base $7$ representation has a sum of digits divisible by $3$. Maybe you meant to exclude the "trivial" case? – Oscar Lanzi Jun 09 '19 at 19:12

3 Answers3

7

Let $a = \sum_{i = 0}^n a_i 7^i$ be a number written in base $7$, that is, $0 \leq a_i \leq 6$. Note that $7^i = (1 + 3 \cdot 2)^i = 1 + 3 b_i$ for some $b_i \geq 0$. Hence $a = \sum_{i = 0}^n a_i + 3 \sum_{i = 0}^n a_i b_i$ is divisible by $3$ if and only if its sum of digits is divisible by $3$. Hence the sum of digits in base $7$ of any prime larger than $3$ will not be divisible by $3$.

Matthias Klupsch
  • 9,512
0

You know: If and only if a number can be devided by three than the sum of its digits to the base of then can be devided by three. Therefore each prime number larger than three has a sum of digits which could not be devided by three.

So what is about the base of $7$: Now when switching from base $10$ to base $7$ you each increase one digit by a multiple of $3$. Therefore the sum of digits modulo three keeps the same. And the statement of above holds for the base $7$ as well.

Alternativly see the multiples of three in the base of $7$

$$3_7, 6_7, 12_7, 15_7, 21_7, 24_7, 30_7, 33_7, 36_7, 42_7,...$$ Each time you "overflow the digit" you have to increase the next digit by $1$ and decrease the current by $4$. So the sum of digits increases by $3$.

Matthias
  • 2,166
0

Do you see that in decimal the divisibility of 9 and 3 is checked by divisibility of sum of the digits for 9 or 3? Similarly you can check divisibility of 15, 5 and 3 in hexadecimal, 7 in octal, 3 in base 4 and 2, 3, 6 in base 7 because this is true for all factors of $b-1$ in base $b$.

Let's say we have a number $N_b$ in base b

$\begin{aligned} N_b &= \overline{a_na_{n-1} \dots a_1a_0}_b = a_nb^n + a_{n-1}b^{n-1} + \dots + a_1b^1 + a_0b^0 \\ &= (a_n + a_{n-1} + \dots + a_0) + \Big[ a_n(b^n-1) + a_{n-1}(b^{n-1}-1) + \dots + a_2(b^2-1) + a_1(b-1) \Big] \end{aligned}$

The latter part has $b^k-1$ in each term, thus is divisible by $b-1$. Hence it's also divisible by all factors of $b-1$. As a result we just need to check the first part which is the sum of all digits to see if it's divisible by that factor of $b-1$ or not

So in base 7 a number is divisible by 6/3/2 if and only if the sum of the digits is divisible by 6/3/2 respectively. Therefore a prime in base 7 can't have its digits accumulated to a multiple of 3.

phuclv
  • 119
  • 10