# Is this an open problem?

I came up with the following question. I could not find a way to solve it, and haven't seen it anywhere also. Is this an open problem?

Problem statement: Consider a prime number p. Consider all numbers having it as a factor. Repeatedly sum the digits of those numbers until you get a number less than or equal to p. In this sequence, will you ever get a p? Is it guaranteed that you get for various values of p (larger ones)?

For example, a "sum" is defined as applying + together on all digits and get the resulting number. You apply "sum" again on it, if it is larger than p, of course.

Thanks Salahuddin

-
Your problem seems to be a wrongly stated one: there's an infinite ammount of numbers having some prime as one of its factors, so how are you going to arrange the sum of digits of all those numbers? Perhaps you did mean to take any number having some prime as a factor, sum its digits and etc.? Don't think so, as then you wouldn't get a "sequence" but only one number. Can you give an example of what you meant? – DonAntonio Nov 14 '12 at 12:43
Take 19 for example as p. Consider such numbers in increasing order, like, 38, 57, 76 etc... This would yield 11, 12, 13, ... etc. "Does this sequence have a 19 anywhere" is a special case of my question. – Salahuddin Nov 14 '12 at 12:48
So is the following your question: Given any prime number $p$ is there a multiple of $p$ such that by iterating the "sum of digits" operation we eventually get $p$? (And I guess this multiple of $p$ shouldn't be $p$ itself.) – arjafi Nov 14 '12 at 12:51
I think I understand now. Well, it happens with $\,p=2,3,5,7,11\,$...I can't say I can deduce something in general. – DonAntonio Nov 14 '12 at 12:53
For $p=19$, it's true for $874$, $1387$, etc. – lhf Nov 14 '12 at 12:56

Let $p$ be a prime other than $2$ or $5$. By Fermat's Theorem, $10^{p-1}\equiv 1\pmod{p}$. Consider the sum $$N=1+10^{p-1}+10^{2(p-1)}+10^{3(p-1)}+\cdots +10^{(p-1)(p-1)}$$ (note there is a total of $p$ terms). Each term in the sum is congruent to $1$ modulo $p$, so $N\equiv 0\pmod{p}$. And the digit sum of $N$ is $p$.

-
Now, of course it answers the question. Also, will there be infinite such numbers, given one always exists? – Salahuddin Nov 14 '12 at 13:22
@Salahuddin: There are infinitely many since we can tack on $0$'s at the end of the decimal expansion of $N$. So to make the question more challenging, we would have to exclude this family. Then I do not know the answer! – André Nicolas Nov 14 '12 at 13:26
What am I missing? You showed that p divides N = (10^(p-1)-1)/9, but this N is (p-1) 1's, not p 1's. – Adam Rubinson Nov 14 '12 at 13:33
@AdamRubinson: You are not missing anything, except that I can't count. – André Nicolas Nov 14 '12 at 13:39
@Salahuddin not really, just a subsequence of this: oeis.org/A069035 – hayd Nov 14 '12 at 20:36

Assume $p\notin\{2,5\}$, in which case $10$ is invertible mod $p$, and its multiplicative order $n$ modulo $p$ is (by definition) such that the power $10^n$ is $1$ modulo $p$ (or one can take $n=p-1$, which will do as well). Now the number $$N=\sum_{i=0}^{p-1}10^{in}$$ has sum of digits $p$ and is divisible by $p$. For $p\in\{2,5\}$ take $N=10p$.

More generally (for $p\notin\{2,5\}$), if $a_1,\ldots,a_p$ are distinct integers, one can take $N=\sum_{i=1}^{p}10^{na_i}$, for infinitely many solutions. Or you could have some repeated entries in the list $a_1,\ldots,a_p$, as long as no value occurs more than $9$ times, to make for a change of all those boring digits $1$ (the digits $0$ remain though).

-
What if we exclude solutions containing only ones and zeroes? – Salahuddin Nov 14 '12 at 14:24
See the last sentence I added. I bet you are now going to ask about solutions that do not use the digits $0$. Or so that it takes at least twice adding up the digits to get to $p$. The point is it is the condition of being divisible by $p$ is not so hard to match, so with varying amounts of effort, I think one can make solutions of all kinds of types. – Marc van Leeuwen Nov 14 '12 at 16:51