Palindromic gapful numbers
- 1 Description (from Rosetta Code)
- 2 Solution
- 3 Case 1. 1st to 20th palindromic gapful numbers
- 4 Case 2. 86th to 100th palindromic gapful numbers
- 5 Case 3. 991st to 1,000th palindromic gapful numbers
- 6 Case 4. 9,995th to 10,000th palindromic gapful numbers
- 7 Case 5. 100,000th palindromic gapful number
- 8 Case 6. 1,000,000th palindromic gapful number
- 9 Case 7. 10,000,000th palindromic gapful number
Description (from Rosetta Code)
| Numbers (positive integers expressed in base ten) that are (evenly) divisible by the number formed by the first and last digit are known as gapful numbers.
All one─ and two─digit numbers have this property and are trivially excluded. Only numbers ≥ 100 will be considered for this Rosetta Code task.
1037 is a gapful number because it is evenly divisible by the number 17 which is formed by the first and last decimal digits of 1037.
A palindromic number is (for this task, a positive integer expressed in base ten), when the number is reversed, is the same as the original number.
The algorithm generates palindromic numbers, and filter them for gapful ones.
In order to generate palindromic numbers, we mirror existing numbers (generators). There are two forms of mirroring, the first one (let us call it incomplete) mirrors every digit but the last one. The complete form mirrors all the digits. See the following examples:
Let us call the number of digits of the generator its order.
The form of generate palindromic numbers in numeric order is to generate mirroring versions of the generator numbers, by order:
|Number of digits of the palindromic numbers||Order of the generators||Mirroring|
So we have to create the generator in ascending order, we start with order 2, first in incomplete form and then in complete form. Once we had finished, we start with the next order, and so on.
For order 2, we have to generate numbers from 100 to 999. For order 3 from 1000 to 1999 and so on. However, we calculate palindrome numbers starting with a given digit, for example, the generator order 3 and starting digit 5 are the numbers 500 to 599. See the following table:
|Starting (or ending) digit|
|2||10 to 19||20 to 29||30 to 39||40 to 49||50 to 59||60 to 69||70 to 79||80 to 89||90 to 99|
|3||100 to 199||200 to 299||300 to 399||400 to 499||500 to 599||600 to 699||700 to 799||800 to 899||900 to 999|
|4||1,000 to 1,999||2,000 to 2,999||3,000 to 3,999||4,000 to 4,999||5,000 to 5,999||6,000 to 6,999||7,000 to 7,999||8,000 to 8,999||9,000 to 9,999|
The formula is:
Once we have palindromic numbers in numeric order, we test every one to be gapful. In order to be gapful, they have to be divisible by the number .
The following function creates a list of the first palindromic gapful numbers (>100) starting/ending with a given digit.
In the program the order is defined in the
The incomplete and complete mirroring are defined in the local function
CreatePalindromes being called with -1 and 0 values, respectively.
As an example, the first 10 palindromic gapful numbers starting/ending with 1:
Case 1. 1st to 20th palindromic gapful numbers
In order to solve the next cases, it is useful to create a matrix, containing the first palindromic gapful numbers, up to a higher number. The first row is for numbers starting/ending with 1, second row for numbers starting/ending with 2, and so on.
With this method, achieving the cases is a matter of extracting numbers from the matrix.
Unfortunately, creating a matrix with the first 10,000,000 numbers was too much for the computer (it would require a 9 x 10,000,000 matrix of numbers). However it was able to create for 1,000,000 numbers. (Even so, it is a 9 x 1,000,000 matrix, or 9,000,000 numbers):
Then, solving the cases (excepting the last one) are now trivial and immediate:
Case 2. 86th to 100th palindromic gapful numbers
Case 3. 991st to 1,000th palindromic gapful numbers
Case 4. 9,995th to 10,000th palindromic gapful numbers
Case 5. 100,000th palindromic gapful number
Case 6. 1,000,000th palindromic gapful number
Case 7. 10,000,000th palindromic gapful number
As it was stated before, We cannot use the matrix method.
The following method requires less memory, because once a row is created (the first 10,000,000 numbers of a given digit), the last one is extracted, and the memory is freed: