Palindromic gapful numbers: Difference between revisions
Content added Content deleted
| Line 2,566: | Line 2,566: | ||
def initialize(digit) |
def initialize(digit) |
||
@digit = digit |
@digit = digit |
||
@nn = @digit * 11 |
@nn = @digit * 11 # digit gapful divisor: 11, 22,...88, 99 |
||
end |
end |
||
def each |
def each |
||
(2..).each do |power| |
(2..).each do |power| |
||
base = 10 |
base = 10**(power >> 1) # value of middle digit position: 10.. |
||
this_lo = base * @digit |
this_lo = base * @digit # starting half for this digit: 10.. to 90.. |
||
next_lo = base * (@digit + 1) |
next_lo = base * (@digit + 1) # starting half for next digit: 20.. to 100.. |
||
this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_10; d_20 |
this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ... |
||
left_half = front_half.to_s |
|||
if power.odd? # for even number of total digits: ab..ba |
|||
palindrome_even = (left_half + left_half.reverse).to_i |
|||
front_half.upto(front_half + 9) do |upper_half| # d_n0 to d_n9 |
|||
palindrome_odd = (left_half.chop + left_half.reverse).to_i |
|||
palindrome_half = upper_half.to_s |
|||
| ⚫ | |||
palindrome = (palindrome_half + palindrome_half.reverse).to_i |
|||
palindrome = palindrome_even + base * i * 11 if power.odd? |
|||
palindrome = palindrome_odd + base * i if power.even? |
|||
end |
|||
| ⚫ | |||
else # for odd number of total digits: ab..m..ba |
|||
palindrome_half = front_half.to_s # d_n0 |
|||
palindrome = (palindrome_half.chop + palindrome_half.reverse).to_i |
|||
# increase palindrome middle digit from ---0--- to ---9--- |
|||
| ⚫ | |||
| ⚫ | |||
palindrome += base # increase middle digit value |
|||
end |
|||
end |
end |
||
end |
end |
||
Revision as of 18:25, 1 June 2020
You are encouraged to solve this task according to the task description, using any language you may know.
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.
Evenly divisible means divisible with no remainder.
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}
(For other ways of expressing the (above) requirements, see the discussion page.
- Related tasks
- Also see
-
- The OEIS entry: A108343 gapful numbers.
C
<lang c>#include <stdbool.h>
- include <stdio.h>
- include <stdint.h>
typedef uint64_t integer;
integer reverse(integer n) {
integer rev = 0;
while (n > 0) {
rev = rev * 10 + (n % 10);
n /= 10;
}
return rev;
}
typedef struct palgen_tag {
integer power; integer next; int digit; bool even;
} palgen_t;
void init_palgen(palgen_t* palgen, int digit) {
palgen->power = 10; palgen->next = digit * palgen->power - 1; palgen->digit = digit; palgen->even = false;
}
integer next_palindrome(palgen_t* p) {
++p->next;
if (p->next == p->power * (p->digit + 1)) {
if (p->even)
p->power *= 10;
p->next = p->digit * p->power;
p->even = !p->even;
}
return p->next * (p->even ? 10 * p->power : p->power)
+ reverse(p->even ? p->next : p->next/10);
}
bool gapful(integer n) {
integer m = n;
while (m >= 10)
m /= 10;
return n % (n % 10 + 10 * m) == 0;
}
void print(int len, integer array[][len]) {
for (int digit = 1; digit < 10; ++digit) {
printf("%d: ", digit);
for (int i = 0; i < len; ++i)
printf(" %llu", array[digit - 1][i]);
printf("\n");
}
}
int main() {
const int n1 = 20, n2 = 15, n3 = 10; const int m1 = 100, m2 = 1000;
integer pg1[9][n1]; integer pg2[9][n2]; integer pg3[9][n3];
for (int digit = 1; digit < 10; ++digit) {
palgen_t pgen;
init_palgen(&pgen, digit);
for (int i = 0; i < m2; ) {
integer n = next_palindrome(&pgen);
if (!gapful(n))
continue;
if (i < n1)
pg1[digit - 1][i] = n;
else if (i < m1 && i >= m1 - n2)
pg2[digit - 1][i - (m1 - n2)] = n;
else if (i >= m2 - n3)
pg3[digit - 1][i - (m2 - n3)] = n;
++i;
}
}
printf("First %d palindromic gapful numbers ending in:\n", n1);
print(n1, pg1);
printf("\nLast %d of first %d palindromic gapful numbers ending in:\n", n2, m1);
print(n2, pg2);
printf("\nLast %d of first %d palindromic gapful numbers ending in:\n", n3, m2);
print(n3, pg3);
return 0;
}</lang>
- Output:
First 20 palindromic gapful numbers ending in: 1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2: 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3: 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4: 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5: 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6: 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7: 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8: 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9: 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069 Last 15 of first 100 palindromic gapful numbers ending in: 1: 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2: 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3: 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4: 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5: 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6: 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7: 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8: 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9: 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569 Last 10 of first 1000 palindromic gapful numbers ending in: 1: 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2: 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3: 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4: 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5: 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6: 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7: 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8: 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869
C++
The idea of generating palindromes first then testing for gapfulness was borrowed from other solutions. <lang cpp>#include <iostream>
- include <cstdint>
typedef uint64_t integer;
integer reverse(integer n) {
integer rev = 0;
while (n > 0) {
rev = rev * 10 + (n % 10);
n /= 10;
}
return rev;
}
// generates base 10 palindromes greater than 100 starting // with the specified digit class palindrome_generator { public:
palindrome_generator(int digit) : power_(10), next_(digit * power_ - 1),
digit_(digit), even_(false) {}
integer next_palindrome() {
++next_;
if (next_ == power_ * (digit_ + 1)) {
if (even_)
power_ *= 10;
next_ = digit_ * power_;
even_ = !even_;
}
return next_ * (even_ ? 10 * power_ : power_)
+ reverse(even_ ? next_ : next_/10);
}
private:
integer power_; integer next_; int digit_; bool even_;
};
bool gapful(integer n) {
integer m = n;
while (m >= 10)
m /= 10;
return n % (n % 10 + 10 * m) == 0;
}
template<size_t len> void print(integer (&array)[9][len]) {
for (int digit = 1; digit < 10; ++digit) {
std::cout << digit << ":";
for (int i = 0; i < len; ++i)
std::cout << ' ' << array[digit - 1][i];
std::cout << '\n';
}
}
int main() {
const int n1 = 20, n2 = 15, n3 = 10; const int m1 = 100, m2 = 1000;
integer pg1[9][n1]; integer pg2[9][n2]; integer pg3[9][n3];
for (int digit = 1; digit < 10; ++digit) {
palindrome_generator pgen(digit);
for (int i = 0; i < m2; ) {
integer n = pgen.next_palindrome();
if (!gapful(n))
continue;
if (i < n1)
pg1[digit - 1][i] = n;
else if (i < m1 && i >= m1 - n2)
pg2[digit - 1][i - (m1 - n2)] = n;
else if (i >= m2 - n3)
pg3[digit - 1][i - (m2 - n3)] = n;
++i;
}
}
std::cout << "First " << n1 << " palindromic gapful numbers ending in:\n"; print(pg1);
std::cout << "\nLast " << n2 << " of first " << m1 << " palindromic gapful numbers ending in:\n"; print(pg2);
std::cout << "\nLast " << n3 << " of first " << m2 << " palindromic gapful numbers ending in:\n"; print(pg3);
return 0;
}</lang>
- Output:
First 20 palindromic gapful numbers ending in: 1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2: 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3: 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4: 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5: 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6: 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7: 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8: 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9: 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069 Last 15 of first 100 palindromic gapful numbers ending in: 1: 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2: 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3: 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4: 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5: 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6: 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7: 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8: 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9: 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569 Last 10 of first 1000 palindromic gapful numbers ending in: 1: 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2: 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3: 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4: 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5: 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6: 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7: 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8: 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869
Crystal
Brute force and slow
<lang ruby>def palindromesgapful(digit, pow)
r1 = (10_u64**pow + 1) * digit
r2 = 10_u64**pow * (digit + 1)
nn = digit * 11
(r1...r2).select { |i| n = i.to_s; n == n.reverse && i % nn == 0 }
end
def digitscount(digit, count)
pow = 2 nums = [] of UInt64 while nums.size < count nums += palindromesgapful(digit, pow) pow += 1 end nums[0...count]
end
count = 20 puts "First 20 palindromic gapful numbers ending with:" (1..9).each { |digit| print "#{digit} : #{digitscount(digit, count)}\n" }
count = 100 puts "\nLast 15 of first 100 palindromic gapful numbers ending in:" (1..9).each { |digit| print "#{digit} : #{digitscount(digit, count).last(15)}\n" }
count = 1000 puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:" (1..9).each { |digit| print "#{digit} : #{digitscount(digit, count).last(10)}\n" }</lang>
Orders of Magnitude Faster: Direct Generation of Numbers
System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.6.13, Crystal 0.34 Run as: $ crystal palindromicgapfuls.cr --release
Optimized version: the ultimate fastest - 36.6 secs <lang ruby>def palindromicgapfuls(digit, count)
gapfuls = [] of UInt64 # array of palindromic gapfuls
nn = digit * 11 # digit gapful divisor: 11, 22,...88, 99
(2..).select do |power|
base = 10_u64**(power >> 1) # value of middle digit position: 10..
this_lo = base * digit # starting half for this digit: 10.. to 90..
next_lo = base * (digit + 1) # starting half for next digit: 20.. to 100..
this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...
palindrome, left_half = 0_u64, front_half.to_s
palindrome_even = (left_half + left_half.reverse).to_u64
palindrome_odd = (left_half.rchop + left_half.reverse).to_u64
10.times do |i|
palindrome = palindrome_even + base * i * 11 if power.odd?
palindrome = palindrome_odd + base * i if power.even?
gapfuls << palindrome if palindrome % nn == 0
return gapfuls if gapfuls.size == count
end
end
end
end
count, keep = 20, 20 puts "First 20 palindromic gapful numbers ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }
count, keep = 100, 15 puts "\nLast 15 of first 100 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }
count, keep = 1_000, 10 puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }
count, keep = 100_000, 1 puts "\n100,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }
count, keep = 1_000_000, 1 puts "\n1,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }
count, keep = 10_000_000, 1 puts "\n10,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }</lang>
Object Oriented implementation: same speed - 37.0 seconds
Here using a Struct (allocated on stack) is faster than using a Class (allocated on heap)
<lang ruby>struct PalindromicGapfuls
include Enumerable(UInt64)
@nn : Int32
def initialize(@digit : Int32) @nn = @digit * 11 # digit gapful divisor: 11, 22,...88, 99 end
def each
(2..).each do |power|
base = 10_u64**(power >> 1) # value of middle digit position: 10..
this_lo = base * @digit # starting half for this digit: 10.. to 90..
next_lo = base * (@digit + 1) # starting half for next digit: 20.. to 100..
this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...
palindrome, left_half = 0_u64, front_half.to_s
palindrome_even = (left_half + left_half.reverse).to_u64
palindrome_odd = (left_half.rchop + left_half.reverse).to_u64
10.times do |i|
palindrome = palindrome_even + base * i * 11 if power.odd?
palindrome = palindrome_odd + base * i if power.even?
yield palindrome if palindrome % @nn == 0
end
end
end
end
end
count, keep = 20, 20 puts "First 20 palindromic gapful numbers ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }
count, keep = 100, 15 puts "\nLast 15 of first 100 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }
count, keep = 1_000, 10 puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }
count, keep = 100_000, 1 puts "\n100,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }
count, keep = 1_000_000, 1 puts "\n1,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }
count, keep = 10_000_000, 1 puts "\n10,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }</lang>
Original version optimized for memory use - 43.0 secs <lang ruby>def palindromicgapfuls(digit, count, keep)
skipped = 0 # initial count of skipped values
to_skip = count - keep # count of unwanted values to skip
gapfuls = [] of UInt64 # array of palindromic gapfuls
nn = digit * 11 # digit gapful divisor: 11, 22,...88, 99
(2..).select do |power|
base = 10_u64 ** (power >> 1) # value of middle digit position: 10..
this_lo = base * digit # starting half for this digit: 10.. to 90..
next_lo = base * (digit + 1) # starting half for next digit: 20.. to 100..
this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...
palindrome, left_half = 0_u64, front_half.to_s
palindrome_even = (left_half + left_half.reverse).to_u64
palindrome_odd = (left_half.rchop + left_half.reverse).to_u64
10.times do |i|
palindrome = palindrome_even + base * i * 11 if power.odd?
palindrome = palindrome_odd + base * i if power.even?
if palindrome % nn == 0
(skipped += 1; next) if skipped < to_skip
gapfuls << palindrome
return gapfuls if gapfuls.size == keep
end
end
end
end
end
count, keep = 20, 20 puts "First 20 palindromic gapful numbers ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
count, keep = 100, 15 puts "\nLast 15 of first 100 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
count, keep = 1_000, 10 puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
count, keep = 100_000, 1 puts "\n100,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
count, keep = 1_000_000, 1 puts "\n1,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
count, keep = 10_000_000, 1 puts "\n10,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }</lang>
OOP version optimized for memory use - 43.0 secs
It creates an output method that skips the unwanted values and only keeps/stores the desired ones.
<lang ruby>struct PalindromicGapfuls
include Enumerable(UInt64)
@nn : Int32
def initialize(@digit : Int32) @nn = @digit * 11 # digit gapful divisor: 11, 22,...88, 99 end
def each
(2..).each do |power|
base = 10_u64**(power >> 1) # value of middle digit position: 10..
this_lo = base * @digit # starting half for this digit: 10.. to 90..
next_lo = base * (@digit + 1) # starting half for next digit: 20.. to 100..
this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...
palindrome, left_half = 0_u64, front_half.to_s
palindrome_even = (left_half + left_half.reverse).to_u64
palindrome_odd = (left_half.rchop + left_half.reverse).to_u64
10.times do |i|
palindrome = palindrome_even + base * i * 11 if power.odd?
palindrome = palindrome_odd + base * i if power.even?
yield palindrome if palindrome % @nn == 0
end
end
end
end
# Optimized output method: only keep desired values.
def keep_from(count, keep)
skipped, to_skip = 0, (count - keep)
kept = [] of UInt64
each do |value|
(skipped += 1; next) if skipped < to_skip
kept << value
return kept if kept.size == keep
end
end
end
count, keep = 20, 20 puts "First 20 palindromic gapful numbers ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }
count, keep = 100, 15 puts "\nLast 15 of first 100 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }
count, keep = 1_000, 10 puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }
count, keep = 100_000, 1 puts "\n100,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }
count, keep = 1_000_000, 1 puts "\n1,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }
count, keep = 10_000_000, 1 puts "\n10,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }</lang>
- Output:
First 20 palindromic gapful numbers 100 ending with: 1 : [121, 1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991, 10901, 11011, 12221, 13431, 14641, 15851, 17171, 18381, 19591] 2 : [242, 2002, 2112, 2222, 2332, 2442, 2552, 2662, 2772, 2882, 2992, 20702, 21912, 22022, 23232, 24442, 25652, 26862, 28182, 29392] 3 : [363, 3003, 3333, 3663, 3993, 31713, 33033, 36663, 300003, 303303, 306603, 309903, 312213, 315513, 318813, 321123, 324423, 327723, 330033, 333333] 4 : [484, 4004, 4224, 4444, 4664, 4884, 40304, 42724, 44044, 46464, 48884, 400004, 401104, 402204, 403304, 404404, 405504, 406604, 407704, 408804] 5 : [5005, 5115, 5225, 5335, 5445, 5555, 5665, 5775, 5885, 5995, 50105, 51315, 52525, 53735, 54945, 55055, 56265, 57475, 58685, 59895] 6 : [6006, 6336, 6666, 6996, 61116, 64746, 66066, 69696, 600006, 603306, 606606, 609906, 612216, 615516, 618816, 621126, 624426, 627726, 630036, 633336] 7 : [7007, 7777, 77077, 700007, 707707, 710017, 717717, 720027, 727727, 730037, 737737, 740047, 747747, 750057, 757757, 760067, 767767, 770077, 777777, 780087] 8 : [8008, 8448, 8888, 80608, 86768, 88088, 800008, 802208, 804408, 806608, 808808, 821128, 823328, 825528, 827728, 829928, 840048, 842248, 844448, 846648] 9 : [9009, 9999, 94149, 99099, 900009, 909909, 918819, 927729, 936639, 945549, 954459, 963369, 972279, 981189, 990099, 999999, 9459549, 9508059, 9557559, 9606069] Last 15 of first 100 palindromic gapful numbers ending in: 1 : [165561, 166661, 167761, 168861, 169961, 170071, 171171, 172271, 173371, 174471, 175571, 176671, 177771, 178871, 179971] 2 : [265562, 266662, 267762, 268862, 269962, 270072, 271172, 272272, 273372, 274472, 275572, 276672, 277772, 278872, 279972] 3 : [30366303, 30399303, 30422403, 30455403, 30488403, 30511503, 30544503, 30577503, 30600603, 30633603, 30666603, 30699603, 30722703, 30755703, 30788703] 4 : [4473744, 4485844, 4497944, 4607064, 4619164, 4620264, 4632364, 4644464, 4656564, 4668664, 4681864, 4693964, 4803084, 4815184, 4827284] 5 : [565565, 566665, 567765, 568865, 569965, 570075, 571175, 572275, 573375, 574475, 575575, 576675, 577775, 578875, 579975] 6 : [60399306, 60422406, 60455406, 60488406, 60511506, 60544506, 60577506, 60600606, 60633606, 60666606, 60699606, 60722706, 60755706, 60788706, 60811806] 7 : [72299227, 72322327, 72399327, 72422427, 72499427, 72522527, 72599527, 72622627, 72699627, 72722727, 72799727, 72822827, 72899827, 72922927, 72999927] 8 : [80611608, 80622608, 80633608, 80644608, 80655608, 80666608, 80677608, 80688608, 80699608, 80800808, 80811808, 80822808, 80833808, 80844808, 80855808] 9 : [95311359, 95400459, 95499459, 95588559, 95677659, 95766759, 95855859, 95944959, 96033069, 96122169, 96211269, 96300369, 96399369, 96488469, 96577569] Last 10 of first 1000 palindromic gapful numbers ending in: 1 : [17799771, 17800871, 17811871, 17822871, 17833871, 17844871, 17855871, 17866871, 17877871, 17888871] 2 : [27799772, 27800872, 27811872, 27822872, 27833872, 27844872, 27855872, 27866872, 27877872, 27888872] 3 : [3084004803, 3084334803, 3084664803, 3084994803, 3085225803, 3085555803, 3085885803, 3086116803, 3086446803, 3086776803] 4 : [482282284, 482414284, 482535284, 482656284, 482777284, 482898284, 482909284, 483020384, 483141384, 483262384] 5 : [57800875, 57811875, 57822875, 57833875, 57844875, 57855875, 57866875, 57877875, 57888875, 57899875] 6 : [6084004806, 6084334806, 6084664806, 6084994806, 6085225806, 6085555806, 6085885806, 6086116806, 6086446806, 6086776806] 7 : [7452992547, 7453223547, 7453993547, 7454224547, 7454994547, 7455225547, 7455995547, 7456226547, 7456996547, 7457227547] 8 : [8085995808, 8086006808, 8086116808, 8086226808, 8086336808, 8086446808, 8086556808, 8086666808, 8086776808, 8086886808] 9 : [9675005769, 9675995769, 9676886769, 9677777769, 9678668769, 9679559769, 9680440869, 9681331869, 9682222869, 9683113869] 100,000th palindromic gapful number ending with: 1 : [178788887871] 2 : [278788887872] 3 : [30878611687803] 4 : [4833326233384] 5 : [578789987875] 6 : [60878611687806] 7 : [74826144162847] 8 : [80869688696808] 9 : [96878077087869] 1,000,000th palindromic gapful number ending with: 1 : [17878799787871] 2 : [27878799787872] 3 : [3087876666787803] 4 : [483333272333384] 5 : [57878799787875] 6 : [6087876996787806] 7 : [7487226666227847] 8 : [8086969559696808] 9 : [9687870990787869] 10,000,000th palindromic gapful number ending with: 1 : [1787878888787871] 2 : [2787878888787872] 3 : [308787855558787803] 4 : [48333332623333384] 5 : [5787878998787875] 6 : [608787855558787806] 7 : [748867523325768847] 8 : [808696968869696808] 9 : [968787783387787869]
Factor
<lang factor>USING: formatting fry io kernel lists lists.lazy locals math math.functions math.ranges math.text.utils prettyprint sequences ; IN: rosetta-code.palindromic-gapful-numbers
! Palindromic numbers are relatively rare compared to gapful ! numbers, so our strategy for finding palindromic gapful ! numbers is to filter gapful numbers from palindromic numbers.
! Palindromic numbers can be generated directly rather than ! filtered or identified from the natural numbers. This is a ! significant speedup since palindromic numbers are relatively ! rare in the natural numbers.
! Here I have used a generation method similar to ! https://www.geeksforgeeks.org/generate-palindromic-numbers-less-n/
! Create a palindrome from its base natural number. ! e.g. 321 t -> 32123 ! 321 f -> 321123
- create-palindrome ( n odd? -- m )
dupd [ 10 /i ] when swap [ over 0 > ] [ 10 * [ 10 /mod ] [ + ] bi* ] while nip ;
! Create an infinite lazy list of palindromic numbers starting ! at 100.
- palindromes ( -- l )
1 lfrom [
10 swap ^ dup 10 * [a,b)
[ [ t create-palindrome ] map ]
[ [ f create-palindrome ] map ] bi
[ sequence>list ] bi@ lappend
] lmap-lazy lconcat ;
! Is an integer gapful?
- gapful? ( n -- ? )
dup 1 digit-groups [ first ] [ last 10 * + ] bi divisor? ;
! Create an infinite lazy list of gapful palindromes.
- gapful-palindromes ( -- l ) palindromes [ gapful? ] lfilter ;
- show-palindromic-gapfuls ( last of -- )
gapful-palindromes :> nums
last of
"~~==[ Last %d of %d palindromic gapful numbers starting at 100 ]==~~\n"
printf 9 [1,b] [| d |
of nums [ 10 mod d = ] lfilter ltake list>array
last tail* d pprint ": " write [ pprint bl ] each nl
] each nl ;
20 20 ! part 1 15 100 ! part 2 10 1000 ! part 3 (Optional) [ show-palindromic-gapfuls ] 2tri@</lang>
- Output:
~~==[ Last 20 of 20 palindromic gapful numbers starting at 100 ]==~~ 1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2: 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3: 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4: 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5: 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6: 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7: 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8: 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9: 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069 ~~==[ Last 15 of 100 palindromic gapful numbers starting at 100 ]==~~ 1: 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2: 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3: 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4: 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5: 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6: 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7: 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8: 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9: 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569 ~~==[ Last 10 of 1000 palindromic gapful numbers starting at 100 ]==~~ 1: 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2: 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3: 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4: 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5: 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6: 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7: 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8: 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869
Fōrmulæ
In this page you can see the solution of this task.
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text (more info). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for transportation effects more than visualization and edition.
The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.
Go
This uses the same strategy as the Factor entry i.e. to generate all palindromic numbers in order and then test whether they're gapful or not.
To keep the Pascal entry company, I've extended the search to the first 10 million such numbers for each of the nine sets. <lang go>package main
import "fmt"
func reverse(s uint64) uint64 {
e := uint64(0)
for s > 0 {
e = e*10 + (s % 10)
s /= 10
}
return e
}
func commatize(n uint) string {
s := fmt.Sprintf("%d", n)
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
return s
}
func ord(n uint) string {
var suffix string
if n > 10 && ((n-11)%100 == 0 || (n-12)%100 == 0 || (n-13)%100 == 0) {
suffix = "th"
} else {
switch n % 10 {
case 1:
suffix = "st"
case 2:
suffix = "nd"
case 3:
suffix = "rd"
default:
suffix = "th"
}
}
return fmt.Sprintf("%s%s", commatize(n), suffix)
}
func main() {
const max = 10_000_000
data := [][3]uint{{1, 20, 7}, {86, 100, 8}, {991, 1000, 10}, {9995, 10000, 12}, {1e5, 1e5, 14},
{1e6, 1e6, 16}, {1e7, 1e7, 18}}
results := make(map[uint][]uint64)
for _, d := range data {
for i := d[0]; i <= d[1]; i++ {
results[i] = make([]uint64, 9)
}
}
var p uint64
outer:
for d := uint64(1); d < 10; d++ {
count := uint(0)
pow := uint64(1)
fl := d * 11
for nd := 3; nd < 20; nd++ {
slim := (d + 1) * pow
for s := d * pow; s < slim; s++ {
e := reverse(s)
mlim := uint64(1)
if nd%2 == 1 {
mlim = 10
}
for m := uint64(0); m < mlim; m++ {
if nd%2 == 0 {
p = s*pow*10 + e
} else {
p = s*pow*100 + m*pow*10 + e
}
if p%fl == 0 {
count++
if _, ok := results[count]; ok {
results[count][d-1] = p
}
if count == max {
continue outer
}
}
}
}
if nd%2 == 1 {
pow *= 10
}
}
}
for _, d := range data {
if d[0] != d[1] {
fmt.Printf("%s to %s palindromic gapful numbers (> 100) ending with:\n", ord(d[0]), ord(d[1]))
} else {
fmt.Printf("%s palindromic gapful number (> 100) ending with:\n", ord(d[0]))
}
for i := 1; i <= 9; i++ {
fmt.Printf("%d: ", i)
for j := d[0]; j <= d[1]; j++ {
fmt.Printf("%*d ", d[2], results[j][i-1])
}
fmt.Println()
}
fmt.Println()
}
}</lang>
- Output:
1st to 20th palindromic gapful numbers (> 100) ending with: 1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2: 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3: 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4: 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5: 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6: 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7: 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8: 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9: 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069 86th to 100th palindromic gapful numbers (> 100) ending with: 1: 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2: 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3: 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4: 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5: 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6: 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7: 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8: 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9: 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569 991st to 1,000th palindromic gapful numbers (> 100) ending with: 1: 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2: 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3: 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4: 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5: 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6: 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7: 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8: 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869 9,995th to 10,000th palindromic gapful numbers (> 100) ending with: 1: 1787447871 1787557871 1787667871 1787777871 1787887871 1787997871 2: 2787447872 2787557872 2787667872 2787777872 2787887872 2787997872 3: 308757757803 308760067803 308763367803 308766667803 308769967803 308772277803 4: 48326662384 48327872384 48329192384 48330303384 48331513384 48332723384 5: 5787447875 5787557875 5787667875 5787777875 5787887875 5787997875 6: 608760067806 608763367806 608766667806 608769967806 608772277806 608775577806 7: 746951159647 746958859647 746961169647 746968869647 746971179647 746978879647 8: 808690096808 808691196808 808692296808 808693396808 808694496808 808695596808 9: 968688886869 968697796869 968706607869 968715517869 968724427869 968733337869 100,000th palindromic gapful number (> 100) ending with: 1: 178788887871 2: 278788887872 3: 30878611687803 4: 4833326233384 5: 578789987875 6: 60878611687806 7: 74826144162847 8: 80869688696808 9: 96878077087869 1,000,000th palindromic gapful number (> 100) ending with: 1: 17878799787871 2: 27878799787872 3: 3087876666787803 4: 483333272333384 5: 57878799787875 6: 6087876996787806 7: 7487226666227847 8: 8086969559696808 9: 9687870990787869 10,000,000th palindromic gapful number (> 100) ending with: 1: 1787878888787871 2: 2787878888787872 3: 308787855558787803 4: 48333332623333384 5: 5787878998787875 6: 608787855558787806 7: 748867523325768847 8: 808696968869696808 9: 968787783387787869
Haskell
Brute Force
<lang haskell>import Control.Monad (guard)
palindromic :: Int -> Bool palindromic n = d == reverse d
where d = show n
gapful :: Int -> Bool gapful n = n `rem` firstLastDigit == 0
where firstLastDigit = read [head asDigits, last asDigits] asDigits = show n
result :: Int -> [Int] result d = do
x <- [(d+100),(d+110)..] guard $ palindromic x && gapful x pure x
showSets :: (Int -> String) -> IO () showSets r = go 1
where go n = if n <= 9 then do putStrLn (show n ++ ": " ++ r n) go (succ n) else pure ()
main :: IO () main = do
putStrLn "\nFirst 20 palindromic gapful numbers ending in:" showSets (show . take 20 . result) putStrLn "\nLast 15 of first 100 palindromic gapful numbers ending in:" showSets (show . drop 85 . take 100 . result) putStrLn "\nLast 10 of first 1000 palindromic gapful numbers ending in:" showSets (show . drop 990 . take 1000 . result) putStrLn "\ndone."</lang>
Optimized
Here the approach is to generate a series of palindromes. <lang haskell>import Data.List (sort)
gapful :: Int -> Bool gapful = (0 ==) . (<*>) rem (read . (<*>) [head, last] . return . show)
toPalinDrome :: Int -> [Int] toPalinDrome n = filter ((&&) . (> 100) <*> gapful) [go n n, go n (n `div` 10)]
where go p 0 = p go p n = go (p * 10 + (n `mod` 10)) (n `div` 10)
gapfulPalindromes :: [Int] gapfulPalindromes = (sort . (=<<) toPalinDrome) [1 .. 99999]
endsWith :: Int -> [Int] endsWith n = filter ((n ==) . (`mod` 10)) gapfulPalindromes
showSets :: (String, [Int] -> [Int]) -> String showSets (k, r) =
k ++
" palindromic gapful numbers ending in:\n" ++
unlines ((<*>) ((++) . show) ((": " ++) . show . r . endsWith) <$> [1 .. 9])
main :: IO () main =
mapM_
(putStrLn . showSets)
[ ("First 20", take 20)
, ("Last 15 of first 100", drop 85 . take 100)
, ("Last 10 of first 1000", drop 990 . take 1000)
]</lang>
- Output:
First 20 palindromic gapful numbers ending in: 1: [121,1001,1111,1221,1331,1441,1551,1661,1771,1881,1991,10901,11011,12221,13431,14641,15851,17171,18381,19591] 2: [242,2002,2112,2222,2332,2442,2552,2662,2772,2882,2992,20702,21912,22022,23232,24442,25652,26862,28182,29392] 3: [363,3003,3333,3663,3993,31713,33033,36663,300003,303303,306603,309903,312213,315513,318813,321123,324423,327723,330033,333333] 4: [484,4004,4224,4444,4664,4884,40304,42724,44044,46464,48884,400004,401104,402204,403304,404404,405504,406604,407704,408804] 5: [5005,5115,5225,5335,5445,5555,5665,5775,5885,5995,50105,51315,52525,53735,54945,55055,56265,57475,58685,59895] 6: [6006,6336,6666,6996,61116,64746,66066,69696,600006,603306,606606,609906,612216,615516,618816,621126,624426,627726,630036,633336] 7: [7007,7777,77077,700007,707707,710017,717717,720027,727727,730037,737737,740047,747747,750057,757757,760067,767767,770077,777777,780087] 8: [8008,8448,8888,80608,86768,88088,800008,802208,804408,806608,808808,821128,823328,825528,827728,829928,840048,842248,844448,846648] 9: [9009,9999,94149,99099,900009,909909,918819,927729,936639,945549,954459,963369,972279,981189,990099,999999,9459549,9508059,9557559,9606069] Last 15 of first 100 palindromic gapful numbers ending in: 1: [165561,166661,167761,168861,169961,170071,171171,172271,173371,174471,175571,176671,177771,178871,179971] 2: [265562,266662,267762,268862,269962,270072,271172,272272,273372,274472,275572,276672,277772,278872,279972] 3: [30366303,30399303,30422403,30455403,30488403,30511503,30544503,30577503,30600603,30633603,30666603,30699603,30722703,30755703,30788703] 4: [4473744,4485844,4497944,4607064,4619164,4620264,4632364,4644464,4656564,4668664,4681864,4693964,4803084,4815184,4827284] 5: [565565,566665,567765,568865,569965,570075,571175,572275,573375,574475,575575,576675,577775,578875,579975] 6: [60399306,60422406,60455406,60488406,60511506,60544506,60577506,60600606,60633606,60666606,60699606,60722706,60755706,60788706,60811806] 7: [72299227,72322327,72399327,72422427,72499427,72522527,72599527,72622627,72699627,72722727,72799727,72822827,72899827,72922927,72999927] 8: [80611608,80622608,80633608,80644608,80655608,80666608,80677608,80688608,80699608,80800808,80811808,80822808,80833808,80844808,80855808] 9: [95311359,95400459,95499459,95588559,95677659,95766759,95855859,95944959,96033069,96122169,96211269,96300369,96399369,96488469,96577569] Last 10 of first 1000 palindromic gapful numbers ending in: 1: [17799771,17800871,17811871,17822871,17833871,17844871,17855871,17866871,17877871,17888871] 2: [27799772,27800872,27811872,27822872,27833872,27844872,27855872,27866872,27877872,27888872] 3: [3084004803,3084334803,3084664803,3084994803,3085225803,3085555803,3085885803,3086116803,3086446803,3086776803] 4: [482282284,482414284,482535284,482656284,482777284,482898284,482909284,483020384,483141384,483262384] 5: [57800875,57811875,57822875,57833875,57844875,57855875,57866875,57877875,57888875,57899875] 6: [6084004806,6084334806,6084664806,6084994806,6085225806,6085555806,6085885806,6086116806,6086446806,6086776806] 7: [7452992547,7453223547,7453993547,7454224547,7454994547,7455225547,7455995547,7456226547,7456996547,7457227547] 8: [8085995808,8086006808,8086116808,8086226808,8086336808,8086446808,8086556808,8086666808,8086776808,8086886808] 9: [9675005769,9675995769,9676886769,9677777769,9678668769,9679559769,9680440869,9681331869,9682222869,9683113869] done.
J
Part 1:
task1 =: {. (((= 10&#:) # ]) palindromic_multiples_of_eleven)
palindromic_multiples_of_eleven =: [: (#~ (99&< *. palindrome&>)) (11*i.100001)&*
palindrome =: (-: |.)@:":
20 task1&> >:i.9
121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591
242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392
363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333
484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804
5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895
6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336
7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087
8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648
9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069
Part 2: <lang> palindromify=: [: , ((,~ |.@}.) ; (,~ |.))&> gapful=: (0 = (|~ ({.,{:)&.(10&#.inv)))&> task2_cartesian_products=: [: , [: { ((i. 10) ; (>: i. 9)) #~ ,&1 task2_palindromes=: [: 10&#.&> [: palindromify task2_cartesian_products task2_gapfuls=: [: /:~ [: ; [: (#~ gapful)@task2_palindromes&.> >:@i. </lang>
palindromify { ;: 'abc XY' NB. demonstration
+---+----+---+----+---+----+---+----+---+----+---+----+
|XaX|XaaX|YaY|YaaY|XbX|XbbX|YbY|YbbY|XcX|XccX|YcY|YccY|
+---+----+---+----+---+----+---+----+---+----+---+----+
NB. task2 solution
A=: task2_gapfuls 4 NB. A is an ordered vector of the 3 to 10 digit gapful palindromes
B=: (</.~ 10&#:) A NB. B are A grouped by last (first) digit
(# , {:)&> B NB. tally and tail of each group
12120 1999999991
12120 2999999992
4044 3999999993
6061 4899999984
12120 5999999995
4044 6999999996
1785 7999449997
3031 8889999888
1352 9999999999
(_15 {. 100&{.)&> B NB. the last 15 of the first hundred
165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971
265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972
30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703
4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284
565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975
60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806
72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927
80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808
95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569
(_10 {. 1000&{.)&> B NB. the last 10 of the first 1000
17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871
27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872
3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803
482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384
57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875
6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806
7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547
8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808
9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869
NB. timing
NB. B matches the rearranged expression
timespacex'assert B -: (</.~ 10&#:) task2_gapfuls 4' NB. approximate timing for the substantial part of the effort
0.551638 7.2343e7
NB. full memory, Thinkpad W540
JVERSION
Engine: j901/j64avx2/windows
Release-c: commercial/2020-01-11T13:29:14
Library: 9.01.20
Platform: Win 64
Installer: J901 install
InstallPath: c:/program files/j901
Contact: www.jsoftware.com
Java
<lang java> import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map;
public class PalindromicGapfulNumbers {
public static void main(String[] args) {
System.out.println("First 20 palindromic gapful numbers ending in:");
displayMap(getPalindromicGapfulEnding(20, 20));
System.out.printf("%nLast 15 of first 100 palindromic gapful numbers ending in:%n");
displayMap(getPalindromicGapfulEnding(15, 100));
System.out.printf("%nLast 10 of first 1000 palindromic gapful numbers ending in:%n");
displayMap(getPalindromicGapfulEnding(10, 1000));
}
private static void displayMap(Map<Integer,List<Long>> map) {
for ( int key = 1 ; key <= 9 ; key++ ) {
System.out.println(key + " : " + map.get(key));
}
}
public static Map<Integer,List<Long>> getPalindromicGapfulEnding(int countReturned, int firstHowMany) {
Map<Integer,List<Long>> map = new HashMap<>();
Map<Integer,Integer> mapCount = new HashMap<>();
for ( int i = 1 ; i <= 9 ; i++ ) {
map.put(i, new ArrayList<>());
mapCount.put(i, 0);
}
boolean notPopulated = true;
for ( long n = 101 ; notPopulated ; n = nextPalindrome(n) ) {
if ( isGapful(n) ) {
int index = (int) (n % 10);
if ( mapCount.get(index) < firstHowMany ) {
map.get(index).add(n);
mapCount.put(index, mapCount.get(index) + 1);
if ( map.get(index).size() > countReturned ) {
map.get(index).remove(0);
}
}
boolean finished = true;
for ( int i = 1 ; i <= 9 ; i++ ) {
if ( mapCount.get(i) < firstHowMany ) {
finished = false;
break;
}
}
if ( finished ) {
notPopulated = false;
}
}
}
return map;
}
public static boolean isGapful(long n) {
String s = Long.toString(n);
return n % Long.parseLong("" + s.charAt(0) + s.charAt(s.length()-1)) == 0;
}
public static int length(long n) {
int length = 0;
while ( n > 0 ) {
length += 1;
n /= 10;
}
return length;
}
public static long nextPalindrome(long n) {
int length = length(n);
if ( length % 2 == 0 ) {
length /= 2;
while ( length > 0 ) {
n /= 10;
length--;
}
n += 1;
if ( powerTen(n) ) {
return Long.parseLong(n + reverse(n/10));
}
return Long.parseLong(n + reverse(n));
}
length = (length - 1) / 2;
while ( length > 0 ) {
n /= 10;
length--;
}
n += 1;
if ( powerTen(n) ) {
return Long.parseLong(n + reverse(n/100));
}
return Long.parseLong(n + reverse(n/10));
}
private static boolean powerTen(long n) {
while ( n > 9 && n % 10 == 0 ) {
n /= 10;
}
return n == 1;
}
private static String reverse(long n) {
return (new StringBuilder(n + "")).reverse().toString();
}
} </lang>
- Output:
First 20 palindromic gapful numbers ending in: 1 : [121, 1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991, 10901, 11011, 12221, 13431, 14641, 15851, 17171, 18381, 19591] 2 : [242, 2002, 2112, 2222, 2332, 2442, 2552, 2662, 2772, 2882, 2992, 20702, 21912, 22022, 23232, 24442, 25652, 26862, 28182, 29392] 3 : [363, 3003, 3333, 3663, 3993, 31713, 33033, 36663, 300003, 303303, 306603, 309903, 312213, 315513, 318813, 321123, 324423, 327723, 330033, 333333] 4 : [484, 4004, 4224, 4444, 4664, 4884, 40304, 42724, 44044, 46464, 48884, 400004, 401104, 402204, 403304, 404404, 405504, 406604, 407704, 408804] 5 : [5005, 5115, 5225, 5335, 5445, 5555, 5665, 5775, 5885, 5995, 50105, 51315, 52525, 53735, 54945, 55055, 56265, 57475, 58685, 59895] 6 : [6006, 6336, 6666, 6996, 61116, 64746, 66066, 69696, 600006, 603306, 606606, 609906, 612216, 615516, 618816, 621126, 624426, 627726, 630036, 633336] 7 : [7007, 7777, 77077, 700007, 707707, 710017, 717717, 720027, 727727, 730037, 737737, 740047, 747747, 750057, 757757, 760067, 767767, 770077, 777777, 780087] 8 : [8008, 8448, 8888, 80608, 86768, 88088, 800008, 802208, 804408, 806608, 808808, 821128, 823328, 825528, 827728, 829928, 840048, 842248, 844448, 846648] 9 : [9009, 9999, 94149, 99099, 900009, 909909, 918819, 927729, 936639, 945549, 954459, 963369, 972279, 981189, 990099, 999999, 9459549, 9508059, 9557559, 9606069] Last 15 of first 100 palindromic gapful numbers ending in: 1 : [165561, 166661, 167761, 168861, 169961, 170071, 171171, 172271, 173371, 174471, 175571, 176671, 177771, 178871, 179971] 2 : [265562, 266662, 267762, 268862, 269962, 270072, 271172, 272272, 273372, 274472, 275572, 276672, 277772, 278872, 279972] 3 : [30366303, 30399303, 30422403, 30455403, 30488403, 30511503, 30544503, 30577503, 30600603, 30633603, 30666603, 30699603, 30722703, 30755703, 30788703] 4 : [4473744, 4485844, 4497944, 4607064, 4619164, 4620264, 4632364, 4644464, 4656564, 4668664, 4681864, 4693964, 4803084, 4815184, 4827284] 5 : [565565, 566665, 567765, 568865, 569965, 570075, 571175, 572275, 573375, 574475, 575575, 576675, 577775, 578875, 579975] 6 : [60399306, 60422406, 60455406, 60488406, 60511506, 60544506, 60577506, 60600606, 60633606, 60666606, 60699606, 60722706, 60755706, 60788706, 60811806] 7 : [72299227, 72322327, 72399327, 72422427, 72499427, 72522527, 72599527, 72622627, 72699627, 72722727, 72799727, 72822827, 72899827, 72922927, 72999927] 8 : [80611608, 80622608, 80633608, 80644608, 80655608, 80666608, 80677608, 80688608, 80699608, 80800808, 80811808, 80822808, 80833808, 80844808, 80855808] 9 : [95311359, 95400459, 95499459, 95588559, 95677659, 95766759, 95855859, 95944959, 96033069, 96122169, 96211269, 96300369, 96399369, 96488469, 96577569] Last 10 of first 1000 palindromic gapful numbers ending in: 1 : [17799771, 17800871, 17811871, 17822871, 17833871, 17844871, 17855871, 17866871, 17877871, 17888871] 2 : [27799772, 27800872, 27811872, 27822872, 27833872, 27844872, 27855872, 27866872, 27877872, 27888872] 3 : [3084004803, 3084334803, 3084664803, 3084994803, 3085225803, 3085555803, 3085885803, 3086116803, 3086446803, 3086776803] 4 : [482282284, 482414284, 482535284, 482656284, 482777284, 482898284, 482909284, 483020384, 483141384, 483262384] 5 : [57800875, 57811875, 57822875, 57833875, 57844875, 57855875, 57866875, 57877875, 57888875, 57899875] 6 : [6084004806, 6084334806, 6084664806, 6084994806, 6085225806, 6085555806, 6085885806, 6086116806, 6086446806, 6086776806] 7 : [7452992547, 7453223547, 7453993547, 7454224547, 7454994547, 7455225547, 7455995547, 7456226547, 7456996547, 7457227547] 8 : [8085995808, 8086006808, 8086116808, 8086226808, 8086336808, 8086446808, 8086556808, 8086666808, 8086776808, 8086886808] 9 : [9675005769, 9675995769, 9676886769, 9677777769, 9678668769, 9679559769, 9680440869, 9681331869, 9682222869, 9683113869]
Julia
<lang julia>import Base.iterate, Base.IteratorSize, Base.IteratorEltype
struct Palindrome x1::UInt8; x2::UInt8; outer::UInt8; end Base.IteratorSize(p::Palindrome) = Base.IsInfinite() Base.IteratorEltype(g::Palindrome) = Vector{Int8}
function Base.iterate(p::Palindrome, state=(UInt8[p.x1]))
arr, len = [p.outer; state; p.outer], length(state)
if all(c -> c == p.x2, state)
return arr, fill(p.x1, len + 1)
end
for i in (len+1)÷2:-1:1
if state[i] < p.x2
state[len - i + 1] = state[i] = state[i] + one(UInt8)
return arr, state
else
state[len - i + 1] = state[i] = p.x1
end
end
state[1] += one(UInt8)
push!(state, state[1])
return arr, state
end
asint(s) = foldl((i, j) -> 10i + j, s) isgapful(a) = mod(asint(a), a[1] * 11) == 0 GapfulPalindrome(i) = Iterators.filter(isgapful, Iterators.take(Palindrome(0, 9, i), 100000000000))
function testpal()
for (lastones, outof) in [(20, 20), (15, 100), (10, 1000), (10, 10000), (10, 100000), (10, 1000000), (10, 10000000)]
@time begin
println("\nLast digit | Last $lastones of $outof palindromic gapful numbers from 100\n",
"-----------|----------------------------------------------------------------------------------------------------------------")
output = fill("", 9)
Threads.@threads for i in 1:9
gplist = sort!(asint.(collect(Iterators.take(GapfulPalindrome(i), outof))))
output[i] = " $i " * string(gplist[end-lastones+1:end]) * "\n"
end
foreach(print, output)
end
end
end
testpal()
</lang>
- Output:
Last digit | Last 20 of 20 palindromic gapful numbers from 100
-----------|------------------------------------------------------------------------------------------------------------------------
1 [121, 1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991, 10901, 11011, 12221, 13431, 14641, 15851, 17171, 18381, 19591]
2 [242, 2002, 2112, 2222, 2332, 2442, 2552, 2662, 2772, 2882, 2992, 20702, 21912, 22022, 23232, 24442, 25652, 26862, 28182, 29392]
3 [363, 3003, 3333, 3663, 3993, 31713, 33033, 36663, 300003, 303303, 306603, 309903, 312213, 315513, 318813, 321123, 324423, 327723, 330033, 333333]
4 [484, 4004, 4224, 4444, 4664, 4884, 40304, 42724, 44044, 46464, 48884, 400004, 401104, 402204, 403304, 404404, 405504, 406604, 407704, 408804]
5 [5005, 5115, 5225, 5335, 5445, 5555, 5665, 5775, 5885, 5995, 50105, 51315, 52525, 53735, 54945, 55055, 56265, 57475, 58685, 59895]
6 [6006, 6336, 6666, 6996, 61116, 64746, 66066, 69696, 600006, 603306, 606606, 609906, 612216, 615516, 618816, 621126, 624426, 627726, 630036, 633336]
7 [7007, 7777, 77077, 700007, 707707, 710017, 717717, 720027, 727727, 730037, 737737, 740047, 747747, 750057, 757757, 760067, 767767, 770077, 777777, 780087]
8 [8008, 8448, 8888, 80608, 86768, 88088, 800008, 802208, 804408, 806608, 808808, 821128, 823328, 825528, 827728, 829928, 840048, 842248, 844448, 846648]
9 [9009, 9999, 94149, 99099, 900009, 909909, 918819, 927729, 936639, 945549, 954459, 963369, 972279, 981189, 990099, 999999, 9459549, 9508059, 9557559, 9606069]
0.623229 seconds (1.68 M allocations: 85.926 MiB, 2.02% gc time)
Last digit | Last 15 of 100 palindromic gapful numbers from 100
-----------|------------------------------------------------------------------------------------------------------------------------
1 [165561, 166661, 167761, 168861, 169961, 170071, 171171, 172271, 173371, 174471, 175571, 176671, 177771, 178871, 179971]
2 [265562, 266662, 267762, 268862, 269962, 270072, 271172, 272272, 273372, 274472, 275572, 276672, 277772, 278872, 279972]
3 [30366303, 30399303, 30422403, 30455403, 30488403, 30511503, 30544503, 30577503, 30600603, 30633603, 30666603, 30699603, 30722703, 30755703, 30788703]
4 [4473744, 4485844, 4497944, 4607064, 4619164, 4620264, 4632364, 4644464, 4656564, 4668664, 4681864, 4693964, 4803084, 4815184, 4827284]
5 [565565, 566665, 567765, 568865, 569965, 570075, 571175, 572275, 573375, 574475, 575575, 576675, 577775, 578875, 579975]
6 [60399306, 60422406, 60455406, 60488406, 60511506, 60544506, 60577506, 60600606, 60633606, 60666606, 60699606, 60722706, 60755706, 60788706, 60811806]
7 [72299227, 72322327, 72399327, 72422427, 72499427, 72522527, 72599527, 72622627, 72699627, 72722727, 72799727, 72822827, 72899827, 72922927, 72999927]
8 [80611608, 80622608, 80633608, 80644608, 80655608, 80666608, 80677608, 80688608, 80699608, 80800808, 80811808, 80822808, 80833808, 80844808, 80855808]
9 [95311359, 95400459, 95499459, 95588559, 95677659, 95766759, 95855859, 95944959, 96033069, 96122169, 96211269, 96300369, 96399369, 96488469, 96577569]
0.011659 seconds (125.64 k allocations: 4.389 MiB)
Last digit | Last 10 of 1000 palindromic gapful numbers from 100
-----------|------------------------------------------------------------------------------------------------------------------------
1 [17799771, 17800871, 17811871, 17822871, 17833871, 17844871, 17855871, 17866871, 17877871, 17888871]
2 [27799772, 27800872, 27811872, 27822872, 27833872, 27844872, 27855872, 27866872, 27877872, 27888872]
3 [3084004803, 3084334803, 3084664803, 3084994803, 3085225803, 3085555803, 3085885803, 3086116803, 3086446803, 3086776803]
4 [482282284, 482414284, 482535284, 482656284, 482777284, 482898284, 482909284, 483020384, 483141384, 483262384]
5 [57800875, 57811875, 57822875, 57833875, 57844875, 57855875, 57866875, 57877875, 57888875, 57899875]
6 [6084004806, 6084334806, 6084664806, 6084994806, 6085225806, 6085555806, 6085885806, 6086116806, 6086446806, 6086776806]
7 [7452992547, 7453223547, 7453993547, 7454224547, 7454994547, 7455225547, 7455995547, 7456226547, 7456996547, 7457227547]
8 [8085995808, 8086006808, 8086116808, 8086226808, 8086336808, 8086446808, 8086556808, 8086666808, 8086776808, 8086886808]
9 [9675005769, 9675995769, 9676886769, 9677777769, 9678668769, 9679559769, 9680440869, 9681331869, 9682222869, 9683113869]
0.121723 seconds (1.31 M allocations: 45.342 MiB, 23.28% gc time)
Last digit | Last 10 of 10000 palindromic gapful numbers from 100
-----------|------------------------------------------------------------------------------------------------------------------------
1 [1787007871, 1787117871, 1787227871, 1787337871, 1787447871, 1787557871, 1787667871, 1787777871, 1787887871, 1787997871]
2 [2787007872, 2787117872, 2787227872, 2787337872, 2787447872, 2787557872, 2787667872, 2787777872, 2787887872, 2787997872]
3 [308745547803, 308748847803, 308751157803, 308754457803, 308757757803, 308760067803, 308763367803, 308766667803, 308769967803, 308772277803]
4 [48322922384, 48323032384, 48324242384, 48325452384, 48326662384, 48327872384, 48329192384, 48330303384, 48331513384, 48332723384]
5 [5787007875, 5787117875, 5787227875, 5787337875, 5787447875, 5787557875, 5787667875, 5787777875, 5787887875, 5787997875]
6 [608748847806, 608751157806, 608754457806, 608757757806, 608760067806, 608763367806, 608766667806, 608769967806, 608772277806, 608775577806]
7 [746931139647, 746938839647, 746941149647, 746948849647, 746951159647, 746958859647, 746961169647, 746968869647, 746971179647, 746978879647]
8 [808686686808, 808687786808, 808688886808, 808689986808, 808690096808, 808691196808, 808692296808, 808693396808, 808694496808, 808695596808]
9 [968652256869, 968661166869, 968670076869, 968679976869, 968688886869, 968697796869, 968706607869, 968715517869, 968724427869, 968733337869]
1.194631 seconds (13.03 M allocations: 452.216 MiB, 19.09% gc time)
Last digit | Last 10 of 100000 palindromic gapful numbers from 100
-----------|------------------------------------------------------------------------------------------------------------------------
1 [178779977871, 178780087871, 178781187871, 178782287871, 178783387871, 178784487871, 178785587871, 178786687871, 178787787871, 178788887871]
2 [278779977872, 278780087872, 278781187872, 278782287872, 278783387872, 278784487872, 278785587872, 278786687872, 278787787872, 278788887872]
3 [30878344387803, 30878377387803, 30878400487803, 30878433487803, 30878466487803, 30878499487803, 30878522587803, 30878555587803, 30878588587803, 30878611687803]
4 [4833228223384, 4833241423384, 4833253523384, 4833265623384, 4833277723384, 4833289823384, 4833290923384, 4833302033384, 4833314133384, 4833326233384]
5 [578780087875, 578781187875, 578782287875, 578783387875, 578784487875, 578785587875, 578786687875, 578787787875, 578788887875, 578789987875]
6 [60878344387806, 60878377387806, 60878400487806, 60878433487806, 60878466487806, 60878499487806, 60878522587806, 60878555587806, 60878588587806, 60878611687806]
7 [74825233252847, 74825333352847, 74825433452847, 74825533552847, 74825633652847, 74825733752847, 74825833852847, 74825933952847, 74826044062847, 74826144162847]
8 [80869599596808, 80869600696808, 80869611696808, 80869622696808, 80869633696808, 80869644696808, 80869655696808, 80869666696808, 80869677696808, 80869688696808]
9 [96877266277869, 96877355377869, 96877444477869, 96877533577869, 96877622677869, 96877711777869, 96877800877869, 96877899877869, 96877988977869, 96878077087869]
10.614688 seconds (129.23 M allocations: 4.349 GiB, 14.81% gc time)
Last digit | Last 10 of 1000000 palindromic gapful numbers from 100
-----------|------------------------------------------------------------------------------------------------------------------------
1 [17878700787871, 17878711787871, 17878722787871, 17878733787871, 17878744787871, 17878755787871, 17878766787871, 17878777787871, 17878788787871, 17878799787871]
2 [27878700787872, 27878711787872, 27878722787872, 27878733787872, 27878744787872, 27878755787872, 27878766787872, 27878777787872, 27878788787872, 27878799787872]
3 [3087873993787803, 3087874224787803, 3087874554787803, 3087874884787803, 3087875115787803, 3087875445787803, 3087875775787803, 3087876006787803, 3087876336787803, 3087876666787803]
4 [483332292233384, 483332303233384, 483332424233384, 483332545233384, 483332666233384, 483332787233384, 483332919233384, 483333030333384, 483333151333384, 483333272333384]
5 [57878700787875, 57878711787875, 57878722787875, 57878733787875, 57878744787875, 57878755787875, 57878766787875, 57878777787875, 57878788787875, 57878799787875]
6 [6087874224787806, 6087874554787806, 6087874884787806, 6087875115787806, 6087875445787806, 6087875775787806, 6087876006787806, 6087876336787806, 6087876666787806, 6087876996787806]
7 [7487217557127847, 7487218558127847, 7487219559127847, 7487220660227847, 7487221661227847, 7487222662227847, 7487223663227847, 7487224664227847, 7487225665227847, 7487226666227847]
8 [8086968668696808, 8086968778696808, 8086968888696808, 8086968998696808, 8086969009696808, 8086969119696808, 8086969229696808, 8086969339696808, 8086969449696808, 8086969559696808]
9 [9687862882687869, 9687863773687869, 9687864664687869, 9687865555687869, 9687866446687869, 9687867337687869, 9687868228687869, 9687869119687869, 9687870000787869, 9687870990787869]
114.847779 seconds (1.28 G allocations: 43.170 GiB, 19.29% gc time)
Last digit | Last 10 of 10000000 palindromic gapful numbers from 100
-----------|------------------------------------------------------------------------------------------------------------------------
1 [1787877997787871, 1787878008787871, 1787878118787871, 1787878228787871, 1787878338787871, 1787878448787871, 1787878558787871, 1787878668787871, 1787878778787871, 1787878888787871]
2 [2787877997787872, 2787878008787872, 2787878118787872, 2787878228787872, 2787878338787872, 2787878448787872, 2787878558787872, 2787878668787872, 2787878778787872, 2787878888787872]
3 [308787828828787803, 308787831138787803, 308787834438787803, 308787837738787803, 308787840048787803, 308787843348787803, 308787846648787803, 308787849948787803, 308787852258787803, 308787855558787803]
4 [48333322822333384, 48333324142333384, 48333325352333384, 48333326562333384, 48333327772333384, 48333328982333384, 48333329092333384, 48333330203333384, 48333331413333384, 48333332623333384]
5 [5787878008787875, 5787878118787875, 5787878228787875, 5787878338787875, 5787878448787875, 5787878558787875, 5787878668787875, 5787878778787875, 5787878888787875, 5787878998787875]
6 [608787828828787806, 608787831138787806, 608787834438787806, 608787837738787806, 608787840048787806, 608787843348787806, 608787846648787806, 608787849948787806, 608787852258787806, 608787855558787806]
7 [748867469964768847, 748867472274768847, 748867479974768847, 748867482284768847, 748867489984768847, 748867492294768847, 748867499994768847, 748867503305768847, 748867513315768847, 748867523325768847]
8 [808696959959696808, 808696960069696808, 808696961169696808, 808696962269696808, 808696963369696808, 808696964469696808, 808696965569696808, 808696966669696808, 808696967769696808, 808696968869696808]
9 [968787702207787869, 968787711117787869, 968787720027787869, 968787729927787869, 968787738837787869, 968787747747787869, 968787756657787869, 968787765567787869, 968787774477787869, 968787783387787869]
1770.411549 seconds (13.02 G allocations: 443.799 GiB, 40.12% gc time)
Pascal
Creating palindromes by adding the right numbers one by one and the precalculated modulus of that numbers
So the numbers to check stays small in bitsize modsum ~16 Bit , n ~ 64 Bit.Dividing is therefore faster
Thinking about it, you don't need n = Uint64, only the value of the digit in that place is enough.
Of course this task has no relevance see digit 9 from 100,000 to 10,000,000
9 : 96878077087869 9 : 9687870990787869 9 : 968787783387787869
<lang pascal>program PalinGap; {$IFDEF FPC}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$CODEALIGN proc=16}{$ALIGN 16}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF} //example 5 digits, digit d // d000d // +00100 10 -times delta[0] aka middle digit //->d010d d020d d030d d040d d050d d060d d070d d080d d090d and // d100d -> not palindromatic //correct by -10x00100 and use the next delta for the next digitplaces // d000d //+ 01010 -> delta[1] // d101d // starting over again with delta[0] until delta[1] is used 10 times type
tLimits = record
LoLmt,HiLmt:Uint64;
end;
const
base = 10;
var
delta : Array[0..9] of Uint64; deltaBase: Array[0..9] of Uint64; deltaMod : Array[0..9] of Uint32; deltaModBase : Array[0..9] of Uint32;
IdxCnt : Array[0..9] of Uint32; ModSum : UInt64; dgtMod : UInt32;
procedure InitDelta(dgt:Byte;dgtCnt:Byte); var
n : Uint64; i,k,mid : NativeInt;
Begin
mid := (dgtCnt-1) DIV 2; //create Add masks For i := 0 to mid do Begin IF ODD(dgtCnt) then
//first 1,101,10001,1000001,100000001,10000000001
Begin
n := 1;
IF i> 0 then
Begin
For k := 1 to i do
n := n*(Base*Base);
inc(n);
end
end
Else //even
// first 11,1001,100001,10000001...
Begin
n := Base;
For k := 1 to i do
n := n*(Base*Base);
inc(n);
end;
// second move to the right place // 1000000,10100000,10001000,10000010,100000001
dgtMod := (dgt*(Base+1));
For k := mid-1 DOWNTO i do
n := n*Base;
delta[i] := n; deltaMod[i]:= n MOD dgtMod; deltaBase[i] := base*n; deltaModBase[i]:= (base*n) MOD dgtMod; end; //counter for digit position For k := 0 to 9 do IdxCnt[k] := Base;
end;
function NextPalin(n : Uint64;dgtcnt:NativeInt):Uint64;inline; var
k,b: NativeInt;
begin
k := 0;
repeat
n := n+delta[k];
inc(ModSum,deltaMod[k]);
b := IdxCnt[k]-1;
IdxCnt[k]:= b;
IF b <> 0 then
break
else
Begin
n := n-deltaBase[k];
dec(ModSum,deltaModBase[k]);
IdxCnt[k]:= Base;
inc(k);
IF k = dgtCnt then
Begin
n := 0;
BREAK;
end;
end;
until false;
NextPalin := n;
end;
procedure OutPalinGap(lowLmt,HiLmt,dgt:NativeInt); var
n : Uint64; i,dgtcnt,mid :NativeInt;
begin
i:=1; write(dgt,' :'); For dgtcnt := 3 to 20 do Begin mid := (dgtcnt-1) shr 1; initDelta(dgt,dgtcnt); n := dgt*delta[mid];// '10...01' -> 'd0...0d' ModSum := n MOD dgtMod;
while (n <>0) AND (i< LowLmt) do
Begin
IF (ModSum MOD dgtMod) = 0 then
Begin
inc(i);
ModSum :=0;//reduce Modsum
end;
n := NextPalin(n,mid);
end;
while (n <>0) AND (i<= HiLmt) do
Begin
IF (ModSum MOD dgtMod) = 0 then
Begin
inc(i);
write(n:dgtcnt+1);
ModSum :=0;//reduce Modsum
end;
n := NextPalin(n,mid);
end;
IF (i > HiLmt) then
BREAK;
end;
writeln;
end;
var
dgt : NativeInt;
begin
writeln('palindromic gapful numbers from 1 to 20');
For dgt := 1 to 9 do
OutPalinGap(1,20,dgt);
writeln;
writeln('palindromic gapful numbers from 86 to 100');
For dgt := 1 to 9 do
OutPalinGap(86,100,dgt);
writeln;
writeln('palindromic gapful numbers from 991 to 1000');
For dgt := 1 to 9 do
OutPalinGap(991,1000,dgt);
writeln;
writeln('palindromic gapful number 100,000');
For dgt := 1 to 9 do
OutPalinGap(100000,100000,dgt);
writeln;
writeln('palindromic gapful number 1,000,000');
For dgt := 1 to 9 do
OutPalinGap(1000000,1000000,dgt);
writeln;
writeln('palindromic gapful number 10,000,000');
For dgt := 1 to 9 do
OutPalinGap(10000000,10000000,dgt);
writeln;
end.</lang>
- Output:
palindromic gapful numbers from 1 to 20 1 : 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2 : 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3 : 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4 : 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5 : 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6 : 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7 : 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8 : 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9 : 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069
palindromic gapful numbers from 86 to 100 1 : 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2 : 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3 : 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4 : 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5 : 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6 : 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7 : 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8 : 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9 : 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569
palindromic gapful numbers from 991 to 1000 1 : 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2 : 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3 : 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4 : 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5 : 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6 : 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7 : 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8 : 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9 : 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869
palindromic gapful number 100,000 1 : 178788887871 2 : 278788887872 3 : 30878611687803 4 : 4833326233384 5 : 578789987875 6 : 60878611687806 7 : 74826144162847 8 : 80869688696808 9 : 96878077087869
palindromic gapful number 1,000,000 1 : 17878799787871 2 : 27878799787872 3 : 3087876666787803 4 : 483333272333384 5 : 57878799787875 6 : 6087876996787806 7 : 7487226666227847 8 : 8086969559696808 9 : 9687870990787869
palindromic gapful number 10,000,000 1 : 1787878888787871 2 : 2787878888787872 3 : 308787855558787803 4 : 48333332623333384 5 : 5787878998787875 6 : 608787855558787806 7 : 748867523325768847 8 : 808696968869696808 9 : 968787783387787869
real 0m4,503s
Phix
Translation of Go, but trimmed back to bare minimum: you should not expect this to fare particularly well at the 10_000_000-level against the likes of Go/Pascal, though it should fare reasonably well against lesser beings... <lang Phix>function reverse_n(atom s)
atom e = 0
while s>0 do
e = e*10 + remainder(s,10)
s = floor(s/10)
end while
return e
end function
constant mx = 1000,
data = {{1, 20, "%7d "}, {86, 100, "%8d "}, {991, 1000, "%10d "}}
include builtins\ordinal.e
procedure main()
sequence results = repeat(repeat({},9),mx)
for d=1 to 9 do -- (the start/end digit)
integer count = 0, pow = 1, fl = d*11
for nd=3 to 15 do -- (number of digits, usually quits early)
-- (obvs. 64-bit phix is fine with 19 digits, but 32-bit ain't)
bool odd = (remainder(nd,2)==1)
for s=d*pow to (d+1)*pow-1 do -- (eg 300 to 399)
integer e = reverse_n(s)
for m=0 to iff(odd?9:0) do -- (1 or 10 iterations)
atom p = e + iff(odd ? s*pow*100+m*pow*10
: s*pow*10)
if remainder(p,fl)==0 then -- gapful!
count += 1
results[count][d] = p
-- (see? goto /is/ sometimes useful :-))
if count==mx then #ilASM{jmp :outer} end if
end if
end for
end for
if odd then pow *= 10 end if
end for
if count<mx then ?9/0 end if -- oh dear...
#ilASM{::outer}
end for
for i=1 to length(data) do
{integer s, integer e, string fmt} = data[i]
printf(1,"%,d%s to %,d%s palindromic gapful numbers (> 100) ending with:\n", {s,ord(s),e,ord(e)})
for d=1 to 9 do
printf(1,"%d: ",d)
for j=s to e do
printf(1,fmt,results[j][d])
end for
printf(1,"\n")
end for
printf(1,"\n")
end for
end procedure main()</lang>
- Output:
1st to 20th palindromic gapful numbers (> 100) ending with: 1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2: 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3: 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4: 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5: 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6: 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7: 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8: 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9: 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069 86th to 100th palindromic gapful numbers (> 100) ending with: 1: 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2: 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3: 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4: 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5: 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6: 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7: 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8: 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9: 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569 991st to 1,000th palindromic gapful numbers (> 100) ending with: 1: 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2: 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3: 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4: 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5: 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6: 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7: 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8: 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869
Prolog
<lang prolog>init_palindrome(Digit, p(10, Next, 0)):-
Next is Digit * 10 - 1.
next_palindrome(Digit, p(Power, Next, Even), p(Power1, Next2, Even1), Palindrome):-
Next1 is Next + 1,
(Next1 is Power * (Digit + 1) ->
(Even == 1 -> Power1 is Power * 10 ; Power1 = Power),
Next2 is Digit * Power1,
Even1 is 1 - Even
;
Power1 = Power,
Next2 = Next1,
Even1 = Even
),
(Even1 == 1 ->
X is 10 * Power1, Y = Next2
;
X = Power1, Y is Next2 // 10
),
reverse_number(Y, Z),
Palindrome is Next2 * X + Z.
reverse_number(N, R):-
reverse_number(N, 0, R).
reverse_number(0, Result, Result):-
!.
reverse_number(N, R, Result):-
R1 is R * 10 + N mod 10, N1 is N // 10, reverse_number(N1, R1, Result).
is_gapful(N):-
is_gapful(N, N).
is_gapful(N, M):-
M < 10, !, 0 is N mod (N mod 10 + 10 * (M mod 10)).
is_gapful(N, M):-
M1 is M // 10, is_gapful(N, M1).
find_palindromic_gapful_numbers(N, List):-
find_palindromic_gapful_numbers(N, 1, List).
find_palindromic_gapful_numbers(_, 10, []):-
!.
find_palindromic_gapful_numbers(N, Digit, [Numbers|Rest]):-
find_palindromic_gapful_numbers1(Digit, N, Numbers), Next_digit is Digit + 1, find_palindromic_gapful_numbers(N, Next_digit, Rest).
find_palindromic_gapful_numbers1(Digit, N, List):-
init_palindrome(Digit, P), find_palindromic_gapful_numbers1(Digit, P, N, 0, List).
find_palindromic_gapful_numbers1(_, _, N, N, []):-
!.
find_palindromic_gapful_numbers1(Digit, P, N, Count, List):-
next_palindrome(Digit, P, P_next, Palindrome),
(is_gapful(Palindrome) ->
Count1 is Count + 1,
List = [Palindrome|Rest]
;
Count1 = Count,
List = Rest
),
find_palindromic_gapful_numbers1(Digit, P_next, N, Count1, Rest).
print_numbers(First, Last, Numbers):-
(First == 1 ->
writef("First %w palindromic gapful numbers ending in:\n", [Last])
;
Count is Last - First + 1,
writef("Last %w of first %w palindromic gapful numbers ending in:\n", [Count, Last])
),
print_numbers(First, Last, 1, Numbers),
nl.
print_numbers(_, _, 10, _):-
!.
print_numbers(First, Last, Digit, [N|Numbers]):-
writef("%w:", [Digit]),
print_numbers1(First, Last, 1, N),
Next_digit is Digit + 1,
print_numbers(First, Last, Next_digit, Numbers).
print_numbers1(_, Last, I, _):-
I > Last, nl, !.
print_numbers1(First, Last, I, [_|Numbers]):-
I < First, !, J is I + 1, print_numbers1(First, Last, J, Numbers).
print_numbers1(First, Last, I, [N|Numbers]):-
writef(" %w", [N]),
J is I + 1,
print_numbers1(First, Last, J, Numbers).
main:-
find_palindromic_gapful_numbers(1000, Numbers), print_numbers(1, 20, Numbers), print_numbers(86, 100, Numbers), print_numbers(991, 1000, Numbers).</lang>
- Output:
First 20 palindromic gapful numbers ending in: First 20 palindromic gapful numbers ending in: 1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2: 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3: 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4: 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5: 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6: 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7: 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8: 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9: 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069 Last 15 of first 100 palindromic gapful numbers ending in: 1: 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2: 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3: 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4: 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5: 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6: 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7: 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8: 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9: 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569 Last 10 of first 1000 palindromic gapful numbers ending in: 1: 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2: 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3: 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4: 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5: 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6: 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7: 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8: 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869
Python
Generators
Uses the technique of:
- generating all odd number of digits palindromes, in order.
- generating all even number of digits palindromes, in order.
- merge sorting those (unbounded) generators.
- then filtering the palindromes for gapful palindromic numbers >= 100
With the number generator the binning was straight-forward.
Runtime is short.
Note: Although this uses the idea of generating palindromes from the Geeks4geeks reference mentioned in the Factor entry, none of their code was used.
<lang python>from itertools import count from pprint import pformat import re import heapq
def pal_part_gen(odd=True):
for i in count(1):
fwd = str(i)
rev = fwd[::-1][1:] if odd else fwd[::-1]
yield int(fwd + rev)
def pal_ordered_gen():
yield from heapq.merge(pal_part_gen(odd=True), pal_part_gen(odd=False))
def is_gapful(x):
return (x % (int(str(x)[0]) * 10 + (x % 10)) == 0)
if __name__ == '__main__':
start = 100
for mx, last in [(20, 20), (100, 15), (1_000, 10)]:
print(f"\nLast {last} of the first {mx} binned-by-last digit "
f"gapful numbers >= {start}")
bin = {i: [] for i in range(1, 10)}
gen = (i for i in pal_ordered_gen() if i >= start and is_gapful(i))
while any(len(val) < mx for val in bin.values()):
g = next(gen)
val = bin[g % 10]
if len(val) < mx:
val.append(g)
b = {k:v[-last:] for k, v in bin.items()}
txt = pformat(b, width=220)
print(, re.sub(r"[{},\[\]]", , txt))</lang>
- Output:
Last 20 of the first 20 binned-by-last digit gapful numbers >= 100 1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2: 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3: 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4: 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5: 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6: 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7: 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8: 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9: 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069 Last 15 of the first 100 binned-by-last digit gapful numbers >= 100 1: 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2: 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3: 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4: 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5: 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6: 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7: 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8: 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9: 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569 Last 10 of the first 1000 binned-by-last digit gapful numbers >= 100 1: 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2: 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3: 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4: 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5: 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6: 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7: 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8: 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869
Functional
<lang python>Palindromic gapful numbers
from itertools import chain, count, islice, tee from functools import reduce
- palindromicGapfuls :: () -> [Int]
def palindromicGapfuls():
A non-finite series of gapful palindromic numbers.
def derived(digitsEven):
A palindrome of an even or odd number of digits,
obtained by appending either all or just the tail
of the reversed digits of n.
def go(x):
s = str(x)
r = s[::-1]
return int((s + r) if digitsEven else (s + r[1:]))
return go
return filter(
lambda n: 0 == n % (int(str(n)[0]) * 10 + (n % 10)),
mergeInOrder(
map(derived(False), count(10))
)(map(derived(True), count(10)))
)
- --------------------------TESTS--------------------------
- main :: IO ()
def main():
Various samples of gapful palindromes grouped by final digit.
tpl = tee(palindromicGapfuls(), 9)
# sample :: (String, Int, Int) -> String
def sample(label, dropped, taken):
return fTable(label)(compose(cons(' '), str))(
compose(unwords, map_(str))
)(
compose(
take(taken),
drop(dropped),
lambda i: filter(
lambda x: i == x % 10,
tpl[i - 1]
)
)
)(enumFromTo(1)(9))
print(
'\n\n'.join(map(lambda x: sample(*x), [
('First 20 samples of gapful palindromes ' +
'(> 100) by last digit:', 0, 20),
('Last 15 of first 100 gapful palindromes ' +
'(> 100) by last digit:', 65, 15),
('Last 10 of first 1000 gapful palindromes ' +
'(> 100) by last digit:', 890, 10)
]))
)
- ------------------------DISPLAY -------------------------
- fTable :: String -> (a -> String) ->
- (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
Heading -> x display function -> fx display function ->
f -> xs -> tabular string.
def go(xShow, fxShow, f, xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
return s + '\n' + '\n'.join(map(
lambda x, y: y.rjust(w, ' ') + ': ' + fxShow(f(x)),
xs, ys
))
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
- ------------------------GENERIC--------------------------
- Just :: a -> Maybe a
def Just(x):
Constructor for an inhabited Maybe (option type) value.
Wrapper containing the result of a computation.
return {'type': 'Maybe', 'Nothing': False, 'Just': x}
- Nothing :: Maybe a
def Nothing():
Constructor for an empty Maybe (option type) value.
Empty wrapper returned where a computation is not possible.
return {'type': 'Maybe', 'Nothing': True}
- compose :: ((a -> a), ...) -> (a -> a)
def compose(*fs):
Composition, from right to left,
of a series of functions.
def go(f, g):
return lambda x: f(g(x))
return reduce(go, fs, lambda x: x)
- cons :: a -> [a] -> [a]
def cons(x):
A list string or iterator constructed
from x as head, and xs as tail.
return lambda xs: [x] + xs if (
isinstance(xs, list)
) else x + xs if (
isinstance(xs, str)
) else chain([x], xs)
- drop :: Int -> [a] -> [a]
def drop(n):
The sublist of xs beginning at
(zero-based) index n.
def go(xs):
take(n)(xs)
return xs
return go
- enumFromTo :: Int -> Int -> [Int]
def enumFromTo(m):
Enumeration of integer values [m..n]
def go(n):
return list(range(m, 1 + n))
return go
- map :: (a -> b) -> [a] -> [b]
def map_(f):
The list obtained by applying f
to each element of xs.
return lambda xs: [f(x) for x in xs]
- mergeInOrder :: Gen [Int] -> Gen [Int] -> Gen [Int]
def mergeInOrder(ga):
An ordered, non-finite, stream of integers
obtained by merging two other such streams.
def go(ma, mb):
a = ma
b = mb
while not a['Nothing'] and not b['Nothing']:
(a1, a2) = a['Just']
(b1, b2) = b['Just']
if a1 < b1:
yield a1
a = uncons(a2)
else:
yield b1
b = uncons(b2)
return lambda gb: go(uncons(ga), uncons(gb))
- take :: Int -> [a] -> [a]
def take(n):
The prefix of xs of length n,
or xs itself if n > length xs.
return lambda xs: list(islice(xs, n))
- uncons :: [a] -> Maybe (a, [a])
def uncons(xs):
The deconstruction of a non-empty list
(or generator stream) into two parts:
a head value, and the remaining values.
nxt = take(1)(xs)
return Just((nxt[0], xs)) if nxt else Nothing()
- unwords :: [String] -> String
def unwords(xs):
A space-separated string derived
from a list of words.
return ' '.join(xs)
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
First 20 samples of gapful palindromes (> 100) by last digit: 1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2: 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3: 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4: 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5: 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6: 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7: 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8: 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9: 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069 Last 15 of first 100 gapful palindromes (> 100) by last digit: 1: 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2: 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3: 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4: 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5: 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6: 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7: 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8: 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9: 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569 Last 10 of first 1000 gapful palindromes (> 100) by last digit: 1: 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2: 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3: 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4: 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5: 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6: 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7: 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8: 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869
Raku
(formerly Perl 6)
<lang perl6>constant @digits = '0','1','2','3','4','5','6','7','8','9';
- Infinite lazy iterator to generate palindromic "gap" numbers
my @npal = flat [ @digits ], [ '00','11','22','33','44','55','66','77','88','99' ],
{
sink @^previous, @^penultimate;
[ flat @digits.map: -> \digit { @penultimate.map: digit ~ * ~ digit } ]
} … *;
- Individual lazy palindromic gapful number iterators for each start/end digit
my @gappal = (1..9).map: -> \digit {
my \divisor = digit + 10 * digit;
@npal.hyper.map: -> \this { next unless (my \test = digit ~ this ~ digit) %% divisor; test }
}
- Display
( "(Required) First 20 gapful palindromes:", ^20, 7
,"\n(Required) 86th through 100th:", 85..99, 8 ,"\n(Optional) 991st through 1,000th:", 990..999, 10 ,"\n(Extra stretchy) 9,995th through 10,000th:", 9994..9999, 12 ,"\n(Meh) 100,000th:", 99999, 14
).hyper(:1batch).map: -> $caption, $range, $fmt {
my $now = now;
say $caption;
put "$_: " ~ @gappal[$_-1][|$range].fmt("%{$fmt}s") for 1..9;
say round( now - $now, .001 ), " seconds";
}</lang>
- Output:
(Required) First 20 gapful palindromes: 1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2: 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3: 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4: 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5: 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6: 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7: 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8: 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9: 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069 0.111 seconds (Required) 86th through 100th: 1: 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2: 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3: 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4: 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5: 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6: 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7: 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8: 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9: 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569 0.046 seconds (Optional) 991st through 1,000th: 1: 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2: 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3: 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4: 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5: 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6: 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7: 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8: 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869 0.282 seconds (Extra stretchy) 9,995th through 10,000th: 1: 1787447871 1787557871 1787667871 1787777871 1787887871 1787997871 2: 2787447872 2787557872 2787667872 2787777872 2787887872 2787997872 3: 308757757803 308760067803 308763367803 308766667803 308769967803 308772277803 4: 48326662384 48327872384 48329192384 48330303384 48331513384 48332723384 5: 5787447875 5787557875 5787667875 5787777875 5787887875 5787997875 6: 608760067806 608763367806 608766667806 608769967806 608772277806 608775577806 7: 746951159647 746958859647 746961169647 746968869647 746971179647 746978879647 8: 808690096808 808691196808 808692296808 808693396808 808694496808 808695596808 9: 968688886869 968697796869 968706607869 968715517869 968724427869 968733337869 3.114 seconds (Meh) 100,000th: 1: 178788887871 2: 278788887872 3: 30878611687803 4: 4833326233384 5: 578789987875 6: 60878611687806 7: 74826144162847 8: 80869688696808 9: 96878077087869 32.603 seconds
REXX
<lang rexx>/*REXX program computes and displays palindromic gapful numbers, it also can show those */ /*─────────────────────── palindromic gapful numbers listed by their last decimal digit.*/ numeric digits 20 /*ensure enough decimal digits gapfuls.*/ parse arg pangaps /*obtain optional arguments from the CL*/ if pangaps= then pangaps= 20 100@@15 1000@@10 /*Not specified? Then use the defaults*/
do until pangaps=; parse var pangaps stuff pangaps; call pangap stuff
end /*until*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ pangap: procedure; parse arg n '@' sp "@" z; #= 0; if sp== then sp= 100
if z== then z= n
@which= ' last '; if z==n then @which= " first "
@pangap#Start= ' palindromic gapful numbers starting at: '
say center(@which z ' of ' n @pangap#Start sp" ", 140, "═")
#.= 0 /*array of result counts for each digit*/
tot= n * 9 /*total # of results that are wanted. */
$.=; sum= 0 /*blank lists; digit results (so far).*/
do j=sp until sum==tot /*loop 'til all digit counters filled. */
if reverse(j) \==j then iterate /*Not a palindrome? Then skip it.*/
parse var j a 2 -1 b /*obtain the first and last dec. digit.*/
if #.b ==n then iterate /*Digit quota filled? Then skip it.*/
if j // (a||b) \==0 then iterate /*Not divisible by A||B? " " " */
sum= sum + 1; #.b= #.b + 1 /*bump the sum counter & digit counter.*/
$.b= $.b j /*append J to the correct list. */
end /*j*/
/* [↓] just show the last Z numbers.*/
do k=1 for 9; say k':' strip( subword($.k, 1 + n - z) )
end /*k*/; say
return</lang>
- output when using the internal default inputs:
(Shown at 5/6 size.)
═════════════════════════════════════ first 20 of 20 palindromic gapful numbers starting at: 100 ══════════════════════════════════════ 1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2: 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3: 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4: 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5: 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6: 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7: 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8: 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9: 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069 ═════════════════════════════════════ last 15 of 100 palindromic gapful numbers starting at: 100 ══════════════════════════════════════ 1: 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2: 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3: 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4: 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5: 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6: 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7: 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8: 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9: 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569 ═════════════════════════════════════ last 10 of 1000 palindromic gapful numbers starting at: 100 ═════════════════════════════════════ 1: 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2: 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3: 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4: 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5: 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6: 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7: 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8: 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869
Ruby
Brute force and slow
<lang ruby>def palindromesgapful(digit, pow)
r1 = digit * (10**pow + 1)
r2 = 10**pow * (digit + 1)
nn = digit * 11
(r1...r2).select { |i| n = i.to_s; n == n.reverse && i % nn == 0 }
end
def digitscount(digit, count)
pow = 2 nums = [] while nums.size < count nums += palindromesgapful(digit, pow) pow += 1 end nums[0...count]
end
count = 20 puts "First 20 palindromic gapful numbers ending with:" (1..9).each { |digit| print "#{digit} : #{digitscount(digit, count)}\n" }
count = 100 puts "\nLast 15 of first 100 palindromic gapful numbers ending in:" (1..9).each { |digit| print "#{digit} : #{digitscount(digit, count).last(15)}\n" }
count = 1000 puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:" (1..9).each { |digit| print "#{digit} : #{digitscount(digit, count).last(10)}\n" }</lang>
Orders of Magnitude Faster: Direct Generation of Numbers
System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.6.13 Run as: $ ruby palindromicgapfuls.rb
Optimized version: the ultimate fastest - Ruby 2.7.1 - 177.0 secs <lang ruby>def palindromicgapfuls(digit, count)
gapfuls = [] # array of palindromic gapfuls
nn = digit * 11 # digit gapful divisor: 11, 22,...88, 99
power = 1 # these two lines will work
while power += 1 # for all Ruby VMs|versions
#(2..).each do |power| # Ruby => 2.6; can replace above 2 lines
base = 10**(power >> 1) # value of middle digit position: 10..
this_lo = base * digit # starting half for this digit: 10.. to 90..
next_lo = base * (digit + 1) # starting half for next digit: 20.. to 100..
this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...
left_half = front_half.to_s
palindrome_even = (left_half + left_half.reverse).to_i
palindrome_odd = (left_half.chop + left_half.reverse).to_i
10.times do |i|
palindrome = palindrome_even + base * i * 11 if power.odd?
palindrome = palindrome_odd + base * i if power.even?
gapfuls << palindrome if palindrome % nn == 0
return gapfuls if gapfuls.size == count
end
end
end
end
count, keep = 20, 20 puts "First 20 palindromic gapful numbers ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }
count, keep = 100, 15 puts "\nLast 15 of first 100 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }
count, keep = 1_000, 10 puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }
count, keep = 100_000, 1 puts "\n100,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }
count, keep = 1_000_000, 1 puts "\n1,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }
count, keep = 10_000_000, 1 puts "\n10,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count).last(keep)}" }</lang>
Object Oriented implementation: Ruby 2.7.1 - 176.0 secs <lang ruby>class PalindromicGapfuls
include Enumerable
def initialize(digit) @digit = digit @nn = @digit * 11 # digit gapful divisor: 11, 22,...88, 99 end
def each
(2..).each do |power|
base = 10**(power >> 1) # value of middle digit position: 10..
this_lo = base * @digit # starting half for this digit: 10.. to 90..
next_lo = base * (@digit + 1) # starting half for next digit: 20.. to 100..
this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...
left_half = front_half.to_s
palindrome_even = (left_half + left_half.reverse).to_i
palindrome_odd = (left_half.chop + left_half.reverse).to_i
10.times do |i|
palindrome = palindrome_even + base * i * 11 if power.odd?
palindrome = palindrome_odd + base * i if power.even?
yield palindrome if palindrome % @nn == 0
end
end
end
end
end
count, keep = 20, 20 puts "First 20 palindromic gapful numbers ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }
count, keep = 100, 15 puts "\nLast 15 of first 100 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }
count, keep = 1_000, 10 puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }
count, keep = 100_000, 1 puts "\n100,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }
count, keep = 1_000_000, 1 puts "\n1,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }
count, keep = 10_000_000, 1 puts "\n10,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).first(count).last(keep)}" }</lang>
Original version optimized for memory use. <lang ruby>def palindromicgapfuls(digit, count, keep)
skipped = 0 # initial count of skipped values
to_skip = count - keep # count of unwanted values to skip
gapfuls = [] # array of palindromic gapfuls
nn = digit * 11 # digit gapful divisor: 11, 22,...88, 99
power = 1 # these two lines will work
while power += 1 # for all Ruby VMs|versions
#(2..).each do |power| # Ruby => 2.6; can replace above 2 lines
base = 10 ** (power >> 1) # value of middle digit position: 10..
this_lo = base * digit # starting half for this digit: 10.. to 90..
next_lo = base * (digit + 1) # starting half for next digit: 20.. to 100..
this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...
left_half = front_half.to_s
palindrome_even = (left_half + left_half.reverse).to_i
palindrome_odd = (left_half.chop + left_half.reverse).to_i
10.times do |i|
palindrome = palindrome_even + base * i * 11 if power.odd?
palindrome = palindrome_odd + base * i if power.even?
if palindrome % nn == 0
(skipped += 1; next) if skipped < to_skip
gapfuls << palindrome
return gapfuls if gapfuls.size == keep
end
end
end
end
end
count, keep = 20, 20 puts "First 20 palindromic gapful numbers ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
count, keep = 100, 15 puts "\nLast 15 of first 100 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
count, keep = 1_000, 10 puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
count, keep = 100_000, 1 puts "\n100,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
count, keep = 1_000_000, 1 puts "\n1,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }
count, keep = 10_000_000, 1 puts "\n10,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{palindromicgapfuls(digit, count, keep)}" }</lang>
OOP version optimized for memory use.
It creates an output method that skips the unwanted values and only keeps/stores the desired ones.
<lang ruby>class PalindromicGapfuls
include Enumerable
def initialize(digit) @digit = digit @nn = @digit * 11 # digit gapful divisor: 11, 22,...88, 99 end
def each
(2..).each do |power|
base = 10**(power >> 1) # value of middle digit position: 10..
this_lo = base * @digit # starting half for this digit: 10.. to 90..
next_lo = base * (@digit + 1) # starting half for next digit: 20.. to 100..
this_lo.step(to: next_lo - 1, by: 10) do |front_half| # d_00; d_10; d_20; ...
left_half = front_half.to_s
palindrome_even = (left_half + left_half.reverse).to_i
palindrome_odd = (left_half.chop + left_half.reverse).to_i
10.times do |i|
palindrome = palindrome_even + base * i * 11 if power.odd?
palindrome = palindrome_odd + base * i if power.even?
yield palindrome if palindrome % @nn == 0
end
end
end
end
# Optimized output method: only keep desired values. # May be marginally faster on some VMs.
def keep_from(count, keep)
skipped, to_skip = 0, (count - keep)
kept = [] # index, kept = 0, Array.new(keep)
each do |value|
(skipped += 1; next) if skipped < to_skip
kept << value # kept[index] = value; index += 1
return kept if kept.size == keep # return kept if index == keep
end
end
end
count, keep = 20, 20 puts "First 20 palindromic gapful numbers ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }
count, keep = 100, 15 puts "\nLast 15 of first 100 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }
count, keep = 1_000, 10 puts "\nLast 10 of first 1000 palindromic gapful numbers ending in:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }
count, keep = 100_000, 1 puts "\n100,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }
count, keep = 1_000_000, 1 puts "\n1,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }
count, keep = 10_000_000, 1 puts "\n10,000,000th palindromic gapful number ending with:" 1.upto(9) { |digit| puts "#{digit} : #{PalindromicGapfuls.new(digit).keep_from(count, keep)}" }</lang>
- Output:
First 20 palindromic gapful numbers 100 ending with: 1 : [121, 1001, 1111, 1221, 1331, 1441, 1551, 1661, 1771, 1881, 1991, 10901, 11011, 12221, 13431, 14641, 15851, 17171, 18381, 19591] 2 : [242, 2002, 2112, 2222, 2332, 2442, 2552, 2662, 2772, 2882, 2992, 20702, 21912, 22022, 23232, 24442, 25652, 26862, 28182, 29392] 3 : [363, 3003, 3333, 3663, 3993, 31713, 33033, 36663, 300003, 303303, 306603, 309903, 312213, 315513, 318813, 321123, 324423, 327723, 330033, 333333] 4 : [484, 4004, 4224, 4444, 4664, 4884, 40304, 42724, 44044, 46464, 48884, 400004, 401104, 402204, 403304, 404404, 405504, 406604, 407704, 408804] 5 : [5005, 5115, 5225, 5335, 5445, 5555, 5665, 5775, 5885, 5995, 50105, 51315, 52525, 53735, 54945, 55055, 56265, 57475, 58685, 59895] 6 : [6006, 6336, 6666, 6996, 61116, 64746, 66066, 69696, 600006, 603306, 606606, 609906, 612216, 615516, 618816, 621126, 624426, 627726, 630036, 633336] 7 : [7007, 7777, 77077, 700007, 707707, 710017, 717717, 720027, 727727, 730037, 737737, 740047, 747747, 750057, 757757, 760067, 767767, 770077, 777777, 780087] 8 : [8008, 8448, 8888, 80608, 86768, 88088, 800008, 802208, 804408, 806608, 808808, 821128, 823328, 825528, 827728, 829928, 840048, 842248, 844448, 846648] 9 : [9009, 9999, 94149, 99099, 900009, 909909, 918819, 927729, 936639, 945549, 954459, 963369, 972279, 981189, 990099, 999999, 9459549, 9508059, 9557559, 9606069] Last 15 of first 100 palindromic gapful numbers ending in: 1 : [165561, 166661, 167761, 168861, 169961, 170071, 171171, 172271, 173371, 174471, 175571, 176671, 177771, 178871, 179971] 2 : [265562, 266662, 267762, 268862, 269962, 270072, 271172, 272272, 273372, 274472, 275572, 276672, 277772, 278872, 279972] 3 : [30366303, 30399303, 30422403, 30455403, 30488403, 30511503, 30544503, 30577503, 30600603, 30633603, 30666603, 30699603, 30722703, 30755703, 30788703] 4 : [4473744, 4485844, 4497944, 4607064, 4619164, 4620264, 4632364, 4644464, 4656564, 4668664, 4681864, 4693964, 4803084, 4815184, 4827284] 5 : [565565, 566665, 567765, 568865, 569965, 570075, 571175, 572275, 573375, 574475, 575575, 576675, 577775, 578875, 579975] 6 : [60399306, 60422406, 60455406, 60488406, 60511506, 60544506, 60577506, 60600606, 60633606, 60666606, 60699606, 60722706, 60755706, 60788706, 60811806] 7 : [72299227, 72322327, 72399327, 72422427, 72499427, 72522527, 72599527, 72622627, 72699627, 72722727, 72799727, 72822827, 72899827, 72922927, 72999927] 8 : [80611608, 80622608, 80633608, 80644608, 80655608, 80666608, 80677608, 80688608, 80699608, 80800808, 80811808, 80822808, 80833808, 80844808, 80855808] 9 : [95311359, 95400459, 95499459, 95588559, 95677659, 95766759, 95855859, 95944959, 96033069, 96122169, 96211269, 96300369, 96399369, 96488469, 96577569] Last 10 of first 1000 palindromic gapful numbers ending in: 1 : [17799771, 17800871, 17811871, 17822871, 17833871, 17844871, 17855871, 17866871, 17877871, 17888871] 2 : [27799772, 27800872, 27811872, 27822872, 27833872, 27844872, 27855872, 27866872, 27877872, 27888872] 3 : [3084004803, 3084334803, 3084664803, 3084994803, 3085225803, 3085555803, 3085885803, 3086116803, 3086446803, 3086776803] 4 : [482282284, 482414284, 482535284, 482656284, 482777284, 482898284, 482909284, 483020384, 483141384, 483262384] 5 : [57800875, 57811875, 57822875, 57833875, 57844875, 57855875, 57866875, 57877875, 57888875, 57899875] 6 : [6084004806, 6084334806, 6084664806, 6084994806, 6085225806, 6085555806, 6085885806, 6086116806, 6086446806, 6086776806] 7 : [7452992547, 7453223547, 7453993547, 7454224547, 7454994547, 7455225547, 7455995547, 7456226547, 7456996547, 7457227547] 8 : [8085995808, 8086006808, 8086116808, 8086226808, 8086336808, 8086446808, 8086556808, 8086666808, 8086776808, 8086886808] 9 : [9675005769, 9675995769, 9676886769, 9677777769, 9678668769, 9679559769, 9680440869, 9681331869, 9682222869, 9683113869] 100,000th palindromic gapful number ending with: 1 : [178788887871] 2 : [278788887872] 3 : [30878611687803] 4 : [4833326233384] 5 : [578789987875] 6 : [60878611687806] 7 : [74826144162847] 8 : [80869688696808] 9 : [96878077087869] 1,000,000th palindromic gapful number ending with: 1 : [17878799787871] 2 : [27878799787872] 3 : [3087876666787803] 4 : [483333272333384] 5 : [57878799787875] 6 : [6087876996787806] 7 : [7487226666227847] 8 : [8086969559696808] 9 : [9687870990787869] 10,000,000th palindromic gapful number ending with: 1 : [1787878888787871] 2 : [2787878888787872] 3 : [308787855558787803] 4 : [48333332623333384] 5 : [5787878998787875] 6 : [608787855558787806] 7 : [748867523325768847] 8 : [808696968869696808] 9 : [968787783387787869]
Sidef
Inspired from the C++ and Raku entries. <lang ruby>class PalindromeGenerator (digit, base=10) {
has power = base has after = (digit*power - 1) has even = false
method next {
if (++after == power*(digit+1)) {
power *= base if even
after = digit*power
even.not!
}
even ? (after*power*base + reverse(after, base))
: (after*power + reverse(after/base, base))
}
}
var task = [
"(Required) First 20 gapful palindromes:", { .first(20) }, 7,
,"\n(Required) 86th through 100th:", { .first(1e2).last(15) }, 8,
,"\n(Optional) 991st through 1,000th:", { .first(1e3).last(10) }, 10,
,"\n(Extra stretchy) 9,995th through 10,000th:", { .first(1e4).last(6) }, 12,
]
task.each_slice(3, {|title, f, w|
say title
for d in (1..9) {
var k = 11*d
var iter = PalindromeGenerator(d)
var arr = f(^Inf->lazy.map { iter.next }.grep {|n| k `divides` n })
say ("#{d}: ", arr.map{ "%*s" % (w, _) }.join(' '))
}
})</lang>
- Output:
(Required) First 20 gapful palindromes: 1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2: 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3: 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4: 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5: 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6: 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7: 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8: 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9: 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069 (Required) 86th through 100th: 1: 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2: 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3: 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4: 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5: 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6: 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7: 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8: 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9: 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569 (Optional) 991st through 1,000th: 1: 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2: 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3: 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4: 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5: 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6: 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7: 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8: 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869 (Extra stretchy) 9,995th through 10,000th: 1: 1787447871 1787557871 1787667871 1787777871 1787887871 1787997871 2: 2787447872 2787557872 2787667872 2787777872 2787887872 2787997872 3: 308757757803 308760067803 308763367803 308766667803 308769967803 308772277803 4: 48326662384 48327872384 48329192384 48330303384 48331513384 48332723384 5: 5787447875 5787557875 5787667875 5787777875 5787887875 5787997875 6: 608760067806 608763367806 608766667806 608769967806 608772277806 608775577806 7: 746951159647 746958859647 746961169647 746968869647 746971179647 746978879647 8: 808690096808 808691196808 808692296808 808693396808 808694496808 808695596808 9: 968688886869 968697796869 968706607869 968715517869 968724427869 968733337869
Wren
Search limited to the first 100,000 palindromic gapful numbers as, beyond that, the numbers become too large (>= 2 ^ 53) to be accurately represented by Wren's Num type. <lang ecmascript>import "/fmt" for Conv, Fmt
var reverse = Fn.new { |s|
var e = 0
while (s > 0) {
e = e * 10 + (s % 10)
s = (s/10).floor
}
return e
}
var MAX = 100000 var data = [ [1, 20, 7], [86, 100, 8], [991, 1000, 10], [9995, 10000, 12], [99996, 100000, 14] ] var results = {} for (d in data) {
for (i in d[0]..d[1]) results[i] = List.filled(9, 0)
} var p for (d in 1..9) {
var next_d = false
var count = 0
var pow = 1
var fl = d * 11
for (nd in 3..19) {
var slim = (d + 1) * pow
for (s in d*pow...slim) {
var e = reverse.call(s)
var mlim = (nd%2 != 1) ? 1 : 10
for (m in 0...mlim) {
if (nd%2 == 0) {
p = s*pow*10 + e
} else {
p = s*pow*100 + m*pow*10 + e
}
if (p%fl == 0) {
count = count + 1
var rc = results[count]
if (rc != null) rc[d-1] = p
if (count == MAX) next_d = true
}
if (next_d) break
}
if (next_d) break
}
if (next_d) break
if (nd%2 == 1) pow = pow * 10
}
}
for (d in data) {
var s1 = Fmt.ordinalize(d[0])
var s2 = Fmt.ordinalize(d[1])
System.print("%(s1) to %(s2) palindromic gapful numbers (> 100) ending with:")
for (i in 1..9) {
System.write("%(i): ")
for (j in d[0]..d[1]) System.write("%(Fmt.d(d[2], results[j][i-1])) ")
System.print()
}
System.print()
}</lang>
- Output:
1st to 20th palindromic gapful numbers (> 100) ending with: 1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2: 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3: 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4: 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5: 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6: 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7: 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8: 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9: 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069 86th to 100th palindromic gapful numbers (> 100) ending with: 1: 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2: 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3: 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4: 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5: 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6: 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7: 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8: 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9: 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569 991st to 1,000th palindromic gapful numbers (> 100) ending with: 1: 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2: 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3: 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4: 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5: 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6: 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7: 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8: 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869 9,995th to 10,000th palindromic gapful numbers (> 100) ending with: 1: 1787447871 1787557871 1787667871 1787777871 1787887871 1787997871 2: 2787447872 2787557872 2787667872 2787777872 2787887872 2787997872 3: 308757757803 308760067803 308763367803 308766667803 308769967803 308772277803 4: 48326662384 48327872384 48329192384 48330303384 48331513384 48332723384 5: 5787447875 5787557875 5787667875 5787777875 5787887875 5787997875 6: 608760067806 608763367806 608766667806 608769967806 608772277806 608775577806 7: 746951159647 746958859647 746961169647 746968869647 746971179647 746978879647 8: 808690096808 808691196808 808692296808 808693396808 808694496808 808695596808 9: 968688886869 968697796869 968706607869 968715517869 968724427869 968733337869 99,996th to 100,000th palindromic gapful numbers (> 100) ending with: 1: 178784487871 178785587871 178786687871 178787787871 178788887871 2: 278784487872 278785587872 278786687872 278787787872 278788887872 3: 30878499487803 30878522587803 30878555587803 30878588587803 30878611687803 4: 4833289823384 4833290923384 4833302033384 4833314133384 4833326233384 5: 578785587875 578786687875 578787787875 578788887875 578789987875 6: 60878499487806 60878522587806 60878555587806 60878588587806 60878611687806 7: 74825733752847 74825833852847 74825933952847 74826044062847 74826144162847 8: 80869644696808 80869655696808 80869666696808 80869677696808 80869688696808 9: 96877711777869 96877800877869 96877899877869 96877988977869 96878077087869
zkl
Using ideas from the Factor entry <lang zkl>// 10,True --> 101,111,121,131,141,151,161,171,181,191,202, .. // 10,False --> 1001,1111,1221,1331,1441,1551,1661,1771,1881,.. fcn createPalindromeW(start,oddLength){ //--> iterator
[start..].tweak('wrap(z){
p,n := z,z;
if(oddLength) n/=10;
while(n>0){ p,n = p*10 + (n%10), n/10; }
p
})
} fcn palindromicGapfulW(endsWith){ //--> iterator
po,pe := createPalindromeW(10,True), createPalindromeW(10,False);
div:=endsWith*10 + endsWith;
Walker.zero().tweak('wrap{
p:=( if(pe.peek()<po.peek()) pe.next() else po.next() );
if(p%10==endsWith and (p%div)==0) p else Void.Skip
})
}</lang> <lang zkl>println("First 20 palindromic gapful numbers:"); [1..9].apply(palindromicGapfulW).apply("walk",20) : pgpp(_);
foreach N,sz in (T( T(100,15), T(1_000,10), )){
println("\nLast %d of %,d palindromic gapful numbers:".fmt(sz,N));
[1..9].apply('wrap(n){ palindromicGapfulW(n).drop(N-sz).walk(sz) }) : pgpp(_);
}
fcn pgpp(table){ // pretty print ( (numbers),(numbers) )
m,fmt := (0).max(table.apply((0).max)).numDigits, "%%%dd ".fmt(m).fmt;
foreach d,row in ([1..].zip(table)){ println(d,": ",row.pump(String,fmt)) }
}</lang>
- Output:
First 20 palindromic gapful numbers: 1: 121 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 10901 11011 12221 13431 14641 15851 17171 18381 19591 2: 242 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 20702 21912 22022 23232 24442 25652 26862 28182 29392 3: 363 3003 3333 3663 3993 31713 33033 36663 300003 303303 306603 309903 312213 315513 318813 321123 324423 327723 330033 333333 4: 484 4004 4224 4444 4664 4884 40304 42724 44044 46464 48884 400004 401104 402204 403304 404404 405504 406604 407704 408804 5: 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 50105 51315 52525 53735 54945 55055 56265 57475 58685 59895 6: 6006 6336 6666 6996 61116 64746 66066 69696 600006 603306 606606 609906 612216 615516 618816 621126 624426 627726 630036 633336 7: 7007 7777 77077 700007 707707 710017 717717 720027 727727 730037 737737 740047 747747 750057 757757 760067 767767 770077 777777 780087 8: 8008 8448 8888 80608 86768 88088 800008 802208 804408 806608 808808 821128 823328 825528 827728 829928 840048 842248 844448 846648 9: 9009 9999 94149 99099 900009 909909 918819 927729 936639 945549 954459 963369 972279 981189 990099 999999 9459549 9508059 9557559 9606069 Last 15 of 100 palindromic gapful numbers: 1: 165561 166661 167761 168861 169961 170071 171171 172271 173371 174471 175571 176671 177771 178871 179971 2: 265562 266662 267762 268862 269962 270072 271172 272272 273372 274472 275572 276672 277772 278872 279972 3: 30366303 30399303 30422403 30455403 30488403 30511503 30544503 30577503 30600603 30633603 30666603 30699603 30722703 30755703 30788703 4: 4473744 4485844 4497944 4607064 4619164 4620264 4632364 4644464 4656564 4668664 4681864 4693964 4803084 4815184 4827284 5: 565565 566665 567765 568865 569965 570075 571175 572275 573375 574475 575575 576675 577775 578875 579975 6: 60399306 60422406 60455406 60488406 60511506 60544506 60577506 60600606 60633606 60666606 60699606 60722706 60755706 60788706 60811806 7: 72299227 72322327 72399327 72422427 72499427 72522527 72599527 72622627 72699627 72722727 72799727 72822827 72899827 72922927 72999927 8: 80611608 80622608 80633608 80644608 80655608 80666608 80677608 80688608 80699608 80800808 80811808 80822808 80833808 80844808 80855808 9: 95311359 95400459 95499459 95588559 95677659 95766759 95855859 95944959 96033069 96122169 96211269 96300369 96399369 96488469 96577569 Last 10 of 1,000 palindromic gapful numbers: 1: 17799771 17800871 17811871 17822871 17833871 17844871 17855871 17866871 17877871 17888871 2: 27799772 27800872 27811872 27822872 27833872 27844872 27855872 27866872 27877872 27888872 3: 3084004803 3084334803 3084664803 3084994803 3085225803 3085555803 3085885803 3086116803 3086446803 3086776803 4: 482282284 482414284 482535284 482656284 482777284 482898284 482909284 483020384 483141384 483262384 5: 57800875 57811875 57822875 57833875 57844875 57855875 57866875 57877875 57888875 57899875 6: 6084004806 6084334806 6084664806 6084994806 6085225806 6085555806 6085885806 6086116806 6086446806 6086776806 7: 7452992547 7453223547 7453993547 7454224547 7454994547 7455225547 7455995547 7456226547 7456996547 7457227547 8: 8085995808 8086006808 8086116808 8086226808 8086336808 8086446808 8086556808 8086666808 8086776808 8086886808 9: 9675005769 9675995769 9676886769 9677777769 9678668769 9679559769 9680440869 9681331869 9682222869 9683113869
<lang zkl>/* We can also thread the whole mess, which for this case, is a 3.75 speed up
* (3 min to 48sec) with 8 cores (Intel 4/4). */
fcn palGT(n,N,sz){ palindromicGapfulW(n).drop(N-sz).walk(sz) } // worker thread foreach N,sz in (T( T(100_000,1) )){
println("\nLast %d of %,d palindromic gapful numbers:".fmt(sz,N));
[1..9].apply('wrap(n){ palGT.future(n,N,sz) }) // create threads
.apply("noop") // wait for threads to finish
: pgpp(_);
}</lang>
- Output:
Last 1 of 100,000 palindromic gapful numbers: 1: 178788887871 2: 278788887872 3: 30878611687803 4: 4833326233384 5: 578789987875 6: 60878611687806 7: 74826144162847 8: 80869688696808 9: 96878077087869