13
$\begingroup$

The smallest number divisible by 7 with seven 7s is trivially 7777777.

Then, what is the greatest 77-digit number divisible by 7 which contains seven 7s?

$\endgroup$
  • 9
    $\begingroup$ Exactly seven 7s, or at least seven 7s? $\endgroup$ – Rand al'Thor Sep 30 at 5:21
  • $\begingroup$ quite ironic this puzzle has seven upvotes (at the time of writing) ;-) $\endgroup$ – happystar Sep 30 at 20:57
  • $\begingroup$ @Randal'Thor No matter. $\endgroup$ – P.-S. Park Oct 2 at 4:53
20
$\begingroup$

Starting with the factoid that

111111 (3 * 7 * 11 * 13 * 37)

is divisible by seven, we can tell that

999999 is too, so if we have any number that's divisible by 7, we can put six nines in front of it and still get a number that's divisible by seven.

So, we can focus on

finding the largest number with 11 digits that's divisible by seven, and has 7 sevens: we can later prepend 66 nines to it.

Being greedy, we should first try the biggest possible such number,

99,997,777,777.

To check its divisibility, we can use the divisibility rules for 7:

we can combine two consecutive sets of 3 digits by subtracting one from the other (this is equivalent to subtracting multiples of 1001, which is divisible by seven), and once we have reached 3 digits, we can subtract twice the last digit from the number formed by the first two.

Both of those operations result in a number that's divisible by seven if and only if they were performed on a number that was divisible by seven. So we get

99,997,777,777 -> 99,997,000,000 -> 99,997 -> 997-99 = 898 -> 89-16 = 73.

Sadly, not a multiple of seven. The next biggest is

99,987,777,777

No luck there, either. The next two are

99,979,777,777 and 99,978,777,777

but alas, no. Moving along in a similar manner, we have to try a couple more until we hit

99,977,787,777 (7 times 14282541111)

which gives the final solution of

69 nines followed by 77787777

| improve this answer | |
$\endgroup$
11
$\begingroup$

It is

$999...99977787777$

We can find this by hand using le p'tit Fermat:
$10^{77} = 10^{13\times 6 - 1} = 10^{-1} = 5 \mod 7$
$10^{8} = 2 \mod 7$
Taking the difference and replacing $0$s with $7$s:
$999...99977777777 = 3 \mod 7$
We need to check increments $2\times 10^7,10^7,2\times 10^6,10^6,2\times 10^5,...$ yielding $6,3,2,1,3,5,1,4,... \mod 7$. So the largest usable increment is $10^4$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I've taken the liberty to change to a more maimstream notation for "modulo". And while at it I also got rid of "I think", your argument is as good as anyone could ask. $\endgroup$ – Paul Panzer Sep 30 at 20:59
  • $\begingroup$ Thanks @PaulPanzer. That is reassuring. $\endgroup$ – Albert.Lang Sep 30 at 21:24
2
$\begingroup$

Brute force solution in Ruby code:

n = 10**77
until (start % 7).zero? && (start.to_s.count('7') == 7) do
  n -= 1
end
n
#=> 99999999999999999999999999999999999999999999999999999999999999999999977787777

| improve this answer | |
$\endgroup$
-1
$\begingroup$

I believe it's:

Sixty-nine 9s followed by 74777777

| improve this answer | |
$\endgroup$
  • $\begingroup$ Why not put the 4 at the end? And maybe then add 203? $\endgroup$ – Jaap Scherphuis Sep 30 at 5:48
  • $\begingroup$ Oh, yeah. I wasn't thinking clearly. $\endgroup$ – Dr Xorile Sep 30 at 6:00

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.