This is Task 2 from project08. If you want any chance that this task will be graded before Midterm 2, you should submit it by 23:00 EST on 2026-11-18 (and earlier if possible).
This is an individual task that you must do on your own.
You can download the starter code for this task using this link.
See how to submit this task using this link.
Put all of your work for this task into the file
remarkableMultiplesFast.py
(which is provided among the starter files)
Remember remarkable multiples task from Project 03? This Project 08 task gives you practice with dictionaries in the context of implementing a stunningly fast way to find smallest remarkable multiples.
Recall that a number is remarkable if its digit sequence consists of a nonempty sequence of 7s followed by a possibly empty sequences of 0s. Examples of remarkable numbers are 7, 70, 77, 700, 770, 777, and 777700.
Here are the first 20 remarkable multiples:
1 * 7 = 7 2 * 35 = 70 3 * 259 = 777 4 * 175 = 700 5 * 14 = 70 6 * 1295 = 7770 7 * 1 = 7 8 * 875 = 7000 9 * 86419753 = 777777777 10 * 7 = 70 11 * 7 = 77 12 * 6475 = 77700 13 * 59829 = 777777 14 * 5 = 70 15 * 518 = 7770 16 * 4375 = 70000 17 * 457516339869281 = 7777777777777777 18 * 432098765 = 7777777770 19 * 40935672514619883 = 777777777777777777 20 * 35 = 700,
In the Project 03 remarkable multiples task you used a brute force algorithm to enumerate multiples of a given positive integer until one had the form of a remarkable number. But this algorithm would take far too long to search for the smallest remarkable multiple for inputs like 17 and 19 above, and even larger remarkable multiples like those below:
17 * 457516339869281 = 7777777777777777 76 * 1023391812865497075 = 77777777777777777700 83 * 937081659973226238286479250334672021419 = 77777777777777777777777777777777777777777 92 * 8454106280193236714975 = 777777777777777777777700 94 * 827423167848699763593380614657210401891252955 = 77777777777777777777777777777777777777777777770 97 * 8018327605956471935853379152348224513172966781214203894616265750286368843069873997709049255441 = 777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777
But now we'll see that by understanding a proof of why every positive integer n has a remarkable multiple, it's possible calculate it smallest possible multiple by examining at most n+1 candidate numbers. So as long as n itself is not too large, this can be done very quickly.
Based on the above facts, here's the proof that every positive integer n has a remarkable multiple.
Let's use the notation 7@k, where k >= 1, to denote a an integer consisting of k 7s. For example:
7@1 = 7
7@2 = 77
7@3 = 777
7@4 = 7777
and so on
Now consider the n+1 numbers of the form 7@k, where 1 <= k <= (n+1). I.e. the numbers {7@1, 7@2, ..., 7@n, 7@(n+1)}.
Each of these n+1 numbers has a remainder with respect to n, i.e., (7@k)%n. But there are only n possible remainders, which are the n integers in the range from 0 to (n-1), inclusive.
By the pigeon-hole principle, if we have (n+1) pigeons that nest in n holes, at least two pigeons must nest in the same hole. This means that at least two of the numbers in the set {7@1, 7@2, ..., 7@n, 7@(n+1)} must have the same remainder r relative to n. I.e., there exist k1, k2 such that 1 <= k1 < k2 <= (n+1) such that (7@k2)%n = r = (7@k1)%n. But this means that (7@k2) - (7@k1) is a multiple of n. Since (7@k2) is a longer sequence of 7s than (7@k1), subtracting the smaller from the larger gives a number begining with (k2-k1) 7s and ending with k1 0s.
As a concrete example, consider n = 96:
So (77777777 - 77777) = 7770000 % 96 = 0, meaning 7770000 is a multiple of 96.
Your goal in this task is to implement a function
findSmallestRemarkableMultipleFast
that efficiently finds that smallest remarkable multiple of n.
findSmallestRemarkableMultipleFast:
Takes a single argument n that you may assume is a positive integer.
Based on the above proof, examines no more than n+1 numbers of the
form 7@k (1 <= k <= n+1) to find and return the smallest
remarkable multiple of n.
Flesh out the skeleton of findSmallestRemarkableMultipleFast in the provided file
remarkableMultiplesFast.py:
findSmallestRemarkableMultipleFast:
findSmallestRemarkableMultipleFast can be quite short.
For example, the body of Prof. Lyn's definitition is 12 lines.
remarkableMultiplesFast.py file and then in Thonny
run the file test_remarkableMultiplesFast.py.
This will test your findSmallestRemarkableMultipleFast function
on all inputs between 1 and 100, inclusive.
It will display a checkmark (✓) for every correct test,
but for a test with a wrong answer will display ✗ and
give details for why the result is incorrect.test_remarkableMultiplesFast.py
change the variable definition VERBOSE = True
to VERBOSE = False.findSmallestRemarkableMultipleFast Examples
The following are some examples that show how findSmallestRemarkableMultipleFast should work:
In []:findSmallestRemarkableMultipleFast(1)Out[]:7
In []:findSmallestRemarkableMultipleFast(2)Out[]:70
In []:findSmallestRemarkableMultipleFast(3)Out[]:777
In []:findSmallestRemarkableMultipleFast(4)Out[]:700
In []:findSmallestRemarkableMultipleFast(5)Out[]:70
In []:findSmallestRemarkableMultipleFast(6)Out[]:7770
In []:findSmallestRemarkableMultipleFast(7)Out[]:7
In []:findSmallestRemarkableMultipleFast(12)Out[]:77700
In []:findSmallestRemarkableMultipleFast(13)Out[]:777777
In []:findSmallestRemarkableMultipleFast(19)Out[]:777777777777777777
In []:findSmallestRemarkableMultipleFast(38)Out[]:7777777777777777770
In []:findSmallestRemarkableMultipleFast(58)Out[]:77777777777777777777777777770
In []:findSmallestRemarkableMultipleFast(72)Out[]:777777777000
In []:findSmallestRemarkableMultipleFast(76)Out[]:77777777777777777700
In []:findSmallestRemarkableMultipleFast(94)Out[]:77777777777777777777777777777777777777777777770
In []:findSmallestRemarkableMultipleFast(96)Out[]:77700000
In []:findSmallestRemarkableMultipleFast(97)Out[]:7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777
findSmallestRemarkableMultipleFast function definition should be
correct:
it should return the correct remarkable multiple for "reasonable" positive integer
inputs. Tests with Thonny show that the algorithm should work for inputs up to
about 4300. After that point, the following error might be encoutered:
ValueError: Exceeds the limit (4300 digits) for integer string conversion;.
findSmallestRemarkableMultipleFast function definition should be
fast:
it should return the correct remarkable multiple for positive integer
inputs in the range 1 to about 4300 immediately.