8
$\begingroup$

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

  • 2
    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?2012-11-14
  • 2
    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.2012-11-14
  • 0
    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.)2012-11-14
  • 0
    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.2012-11-14
  • 1
    For $p=19$, it's true for $874$, $1387$, etc.2012-11-14
  • 0
    yes, the description is right. I could also see for lower primes, (for digit primes, it can be deduced using the criteria for "remainder when a number is divided with 9") but higher ones like 19, that does not work.2012-11-14
  • 0
    expand your base to 100 and the number divided by 99 (same principle there)2012-11-14
  • 0
    I don't see why we only consider primes? http://oeis.org/A0690352012-11-14
  • 0
    yea, ok. It is a subsequence of existing one, yes. @ratchet freak: Expanding base to 100 is nice, looks like it is solvable like that, not considering 1s and zeroes solutions also. ok, got it.2012-11-15

2 Answers 2

15

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$.

  • 0
    Now, of course it answers the question. Also, will there be infinite such numbers, given one always exists?2012-11-14
  • 0
    @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!2012-11-14
  • 0
    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.2012-11-14
  • 1
    @AdamRubinson: You are not missing anything, except that I can't count.2012-11-14
  • 0
    @AdamRubinson: Thanks for pointing out the miscount. I have fixed the solution.2012-11-14
  • 0
    I like that answer. So for example for p = 7 you would get N = 1,000,000,100,000,010,000,001,000,000,100,000,010,000,0012012-11-14
  • 0
    @AdamRubinson: Unfortunately kind of long! It would be interesting to see whether there is a systematic way to find much smaller $N$'s with $p$ $1$'s that have the required property, say of length less than constant times $p$, instead of $N$ of size about $p^2$ that the above procedure gives. Have some ideas but nothing solid.2012-11-14
  • 0
    Yes. The most obvious question is: given p, what is the smallest N? Maybe there is already such a sequence on that website with all the sequences, but I have no idea.2012-11-14
  • 0
    And, excluding these type of numbers (only powers of 10 summed), are there other solutions? And, are there infinitely many such solutions, not counting multiplication by 10 on existing numbers. Will this be a new sequence on Sloan, what Adam mentioned, we need to see (This is Exciting).2012-11-14
  • 0
    It looks like it is a new sequence at OEIS [link](http://oeis.org/search?q=20%2C+12%2C+50%2C+70%2C+&language=english&go=Search).2012-11-14
  • 1
    @Salahuddin not really, just a subsequence of this: http://oeis.org/A0690352012-11-14
1

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).

  • 0
    What if we exclude solutions containing only ones and zeroes?2012-11-14
  • 0
    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.2012-11-14