2
$\begingroup$

Beatriz Viterbo has called a positive integer which is not divisible by any of the ($2^n$, where $n$ is the number of its digits) numbers that result by introducing a plus or minus sign to the left of each of its digits a hopeless number.

Are there infinitely many hopeless numbers? Are there arbitrarily long strings of consecutive numbers all of which are hopeless?

$\endgroup$
  • $\begingroup$ Ask a check for understanding, $100$ would not be a hopeless number because $100$ divides $1+0+0 = 1$. $\endgroup$ – D.B. Mar 29 at 2:47
  • 2
    $\begingroup$ ...because 1+0+0 divides 100. $\endgroup$ – Bernardo Recamán Santos Mar 29 at 2:48
  • 1
    $\begingroup$ Aren't $85$, $850$, $8500$, etc. all hopeless? $\endgroup$ – Barry Cipra Mar 29 at 2:50
  • 2
    $\begingroup$ Also, any odd number whose digit sum is even is hopeless, since minus signs don't change the parity of the digit sum. $\endgroup$ – Barry Cipra Mar 29 at 3:01
  • 1
    $\begingroup$ @coffeemath: I misunderstood the definition. I missed that the condition demanding "signed sum" of the digits be a divisor. I though the individual digits should be divisors. $\endgroup$ – P Vanchinathan Mar 29 at 8:33
2
$\begingroup$

There cannot be more than $17$ consecutive hopeless numbers. This is because among any ten consecutive numbers, one of them must end in a $0$, and for any number, there is a signed digit sum between $0$ and $9$. (The latter fact is easily proved by induction.) If $N=10n$ and $0\le s\le9$ is one of its signed digit sums, then $N+1$ is hopeful if $s=0$, while $N+s-1$ is hopeful if $1\le s\le9$. That is, one of the next $8$ numbers has $1$ among its signed digit sums.

It would be of interest (to me, at least) to know what is the largest possible length of a consecutive string of hopeless numbers (with one or more explicit examples), as well as the largest length that occurs infinitely often. (The sequence $850,851,8500,8501,85000,85001,\ldots$ shows there are infinitely many consecutive pairs of hopeless numbers. Are there infinitely many consecutive triples?)

$\endgroup$
  • 1
    $\begingroup$ The nine integers from $88695$ to $88703$ are all hopeless; there is no longer string up to $10^8$. For any $n$ which is not a multiple of $6$, $5\cdot10^n + 1$, $5\cdot10^n + 2$, $5\cdot10^n + 3$ are three consecutive hopeless numbers. $\endgroup$ – FredH Mar 29 at 17:08
  • 1
    $\begingroup$ @FredH, cool. How did you find the nine-number stretch? $\endgroup$ – Barry Cipra Mar 29 at 17:43
  • 2
    $\begingroup$ Brute force search. $\endgroup$ – FredH Mar 29 at 17:51
  • $\begingroup$ @BarryCipra I wonder: are most numbers hopeless? $\endgroup$ – Bernardo Recamán Santos Mar 30 at 15:23
  • 2
    $\begingroup$ @BernardoRecamánSantos, good question. The first thing to do is compile a list of the first few dozen hopeless numbers and check in with the OEIS. Since odd numbers with an even digit sum are guaranteed to be hopeless, I would expect the density to be at least $1/4$. On the other hand, I would expect most numbers (with a large number of nonzero digits) that have an odd digit sum to include $1$ among their signed digit sums, so the "hopeful" numbers ought to have density at least $1/2$. $\endgroup$ – Barry Cipra Mar 30 at 19:42
1
$\begingroup$

Notation : given $a$, we call any number formed by inserting $\pm$ signs to the left of every number and evaluating, a "resultant" of $a$. Note that the set of resultants is symmetric i.e. $b$ is a resultant of $a$ if and only if $-b$ is (by switching signs) so we focus on just the positive resultants.

Note that if $a$ has an even number of digits, and all its digits are odd, then any resultant is even, and therefore clearly cannot divide $a$. Hence, $a$ is hopeless. One can see just from here that the number of hopeless numbers is infinite. E.g. $79,97,1531$ are all hopeless.

Furthermore, let $a$ be hopeless. Then, consider $10^ka$ for any $k \geq 1$. Note that the resultants of $10^ka$ coincide with the resultants of $a$. The factors of $10^ka$ are the original factors of $a$ multiplied by powers of $2$ and $5$ less than $k$. Suppose all resultants of $a$ are coprime to $2$ and $5$. Then, certainly none of these can be a factor of $10^ka$ as well, rendering $10^ka$ hopeless.

For example, consider a non-trivial hopeless number $74$. Its resultants are $11$ and $3$ (we can leave the negative resultants out),none of which are divisors of $74$, and both of which are coprime to $2$ and $5$. Consequently, the numbers $74\times 10^k$ gives an infinite family of hopeless numbers.

Other families of hopeless numbers can be formed by looking at large enough squares of primes, because the only divisors of such a number are the number, the prime and $1$. If somehow $1$ is not a resultant of such a number (remains to be seen when we can be sure of this) then the number is hopeless. Note that we can rephrase "$1$ is a resultant" as "there are two subsets of digits of $a$ whose difference is $1$".

To make the enough above precise, consider any number bigger than $37$. The resultants of its square cannot be more than $9$ times twice its number of digits, which if the number is $> 37$ ensures that no resultant can reach the number. Therefore, we may search in this domain. Hopeless numbers are easily found , like $41^2 = 1681,43^2 = 1849$ etc. (We cannot say if there are infinitely many of these, however).

$\endgroup$
  • $\begingroup$ In your example for $74$ don't you mean to say that it is not divisible by $11$ or $3$? [you wrote that neither $11$ nor $3$ is a multiple of $74.$] $\endgroup$ – coffeemath Mar 29 at 7:43
  • 1
    $\begingroup$ I don't know how many times I have confused divisor and multiple. Its been an issue for sixteen years and counting! $\endgroup$ – астон вілла олоф мэллбэрг Mar 29 at 9:09
0
$\begingroup$

астон вілла олоф мэллбэрг answers the first question (there are infinitely many hopeless numbers).

For your second question, the answer is "no", there are not arbitrarily long sets of consecutive hopeless numbers. To see this, we will show that any positive integer has a resultant in the set $\{1,2,3,4,5,6,7,8,9,10,12,14,16,18\}$. It follows that any number divisible by $5040$ is not hopeless, and in particular there can never be $5040$ consecutive hopeless numbers.

To see this, insert signs $\pm$ one by one. For each sign except the sign before the last non-zero digit, choose the sign to minimise the absolute value of the sum so far. This means each such sum will be in the interval $[-9,+9]$. For the sign before the last non-zero digit, make sure the sum is non-zero, but if both possibilities are non-zero, choose the smaller absolute value. The only way you can be forced to choose a number with absolute value greater than $9$ is if the final non-zero digit is the same absolute value as the sum so far, in which case the absolute value of the final sum will be twice this (so even and at most $18$). Finally, if the sum is negative go back and swap all signs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.