Instructions for remarkableMultiplesFast

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)

Introduction

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.

The Proof

This proof requires understanding the following mathematical facts, in which all numbers mentioned are assumed to be positive integers:

  1. m is a multiple of n if and only if m = q*n, where q is the positive integer m//n
  2. Suppose m1 and m2 are positive integers where m2 > m1 and m2 and m1 have the same remainder mod n. I.e. (m2 % n) == r == (m1 % n). Then (m2 - m1) is a multiple of n. To see why this is true:
    • If (m2 % n) == r, then m2 = q2*n + r, where q2 is m2//n
    • Similarly, if (m1 % n) == r, then m1 = q1*n + r, where q1 is m1//n.
    • So (m2 - m1) = (q2*n + r) - (q1*n + r) = (q2-q1)*n, which means that (m2 - m1) is a multiple of n.

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:

  • k2 = 8: (7@k2) = 77777777, 77777777 % 96 = 17
  • k1 = 5: (7@k1) = 77777, 77777 % 96 = 17

So (77777777 - 77777) = 7770000 % 96 = 0, meaning 7770000 is a multiple of 96.

Your Task

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:

Notes

  • Here are the key ideas for findSmallestRemarkableMultipleFast:
    • Consider at most the (n+1) integers in the sequence 7@1, 7@2, ..., 7@n, 7@(n+1), in increasing order. There are several ways to do this; pick one.
    • For each integer in this seqeunce, find its remainder mod n.
      • You can use a dictionary to keep track if a previous integer in this seqeuence had the same reminder. What do you do in this case? Hint: you only need to associate a single integer (not a list of integers) with the remainder.
      • What do you do in the special case where the remainder is zero?
    • One a remarkable multiple is found, return it immediately. This means you won't necessarily examine all numbers in the sequence 7@1, 7@2, ..., 7@n, 7@(n+1).
  • You are not allowed to define or use any additional helper functions.
  • The body of findSmallestRemarkableMultipleFast can be quite short. For example, the body of Prof. Lyn's definitition is 12 lines.
  • You should strive to make your code as understandable as possible, using comments to explain any aspects of your code that are not obvious.
  • Test your definition as follows:
  • Save your 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.
  • The test cases print verbosely, showing both the input and output of each test. This is so you can easily tell that it successfully tests all inputs from 1 to 100 without hanging in an case that takes a long time. To remove the verbose output, near the top of the file test_remarkableMultiplesFast.py change the variable definition VERBOSE = True to VERBOSE = False.
  • In this problem, the notion of "remarkable" depends on the special digit 7. But it turns out that the digit repeated before the 0s can be any digit in the range 1 to 9, inclusive. It's easy to generalize the algorithm so that it takes the digit as a parameter.

Examples

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

Rubric

This task does not have an explicit list of rubric items. But here are some things to focus on:
  • Your 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;.
  • Your 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.
  • Your definition should be easy to understand. Use comments and parameters/variables with well-chosen, meaningful names to make it clear why the function calculates the correct result.
  • Your definition should follow the do not repeat yourself (DRY) principle to avoid unnecessary repetition of code patterns.
  • The skelton definition already has a good docstring, which you do not have to modify.