Palindromic gapful numbers

From Fōrmulæ wiki
Jump to: navigation, search

This page is a solution to the task Palindromic gapful numbers in the Rosetta Code, written in Fōrmulæ.

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.

Example

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.

Task

  • Show (nine sets) the first 20 palindromic gapful numbers that end with:
  • The digit 1
  • The digit 2
  • The digit 3
  • ··· ···
  • The digit 9
  • Show (nine sets, like above) of palindromic gapful numbers:
  • The last 15 palindromic gapful numbers (out of 100)
  • The last 10 palindromic gapful numbers (out of 1,000) {optional}

Related tasks:

Also see:

Solution

Explanation

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:

Generator Incomplete Complete
25 252 2,552
407 40,704 407,704
1,357 1,357,531 13,577,531

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
3 2 Incomplete
4 2 Complete
5 3 Incomplete
6 3 Complete
7 4 Incomplete
8 4 Complete
 :  :  :

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
Order 1 2 3 4 5 6 7 8 9
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 .

Program

The following function creates a list of the first palindromic gapful numbers (>100) starting/ending with a given digit.

PalindromicGapfulNumbersCode01.png

In the program the order is defined in the g symbol.

The incomplete and complete mirroring are defined in the local function CreatePalindromes being called with -1 and 0 values, respectively.

Example

As an example, the first 10 palindromic gapful numbers starting/ending with 1:

PalindromicGapfulNumbersExample01.png

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):

PalindromicGapfulNumbersCase01.png

Then, solving the cases (excepting the last one) are now trivial and immediate:

PalindromicGapfulNumbersCase02.png

Case 2. 86th to 100th palindromic gapful numbers

PalindromicGapfulNumbersCase03.png

Case 3. 991st to 1,000th palindromic gapful numbers

PalindromicGapfulNumbersCase04.png

Case 4. 9,995th to 10,000th palindromic gapful numbers

PalindromicGapfulNumbersCase05.png

Case 5. 100,000th palindromic gapful number

PalindromicGapfulNumbersCase06.png

Case 6. 1,000,000th palindromic gapful number

PalindromicGapfulNumbersCase07.png

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:

PalindromicGapfulNumbersCase08.png