Someone in the Rust forum did a version to numerically form the palindromes to eliminate the number<->string conversions, and I did the equivalent for Crystal. The times are literally the same now, and almost 2.5x faster (from ~25.5s to ~9.3s for Crystal). Here’s the code.
Crystal:
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, base = digit * 11, 1_u64 # digit gapful divisor: 11, 22,...88, 99
(2..).select do |power|
base *= 10 if power.even? # value of middle digit position: 10..
base11 = base * 11 # value of middle two digits positions: 110..
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; ...
basep = power.odd? ? base11 : base
palindrome = make_palindrome(front_half, power)
10.times do
(gapfuls << palindrome if (skipped += 1) > to_skip) if palindrome.divisible_by?(nn)
palindrome += basep
end
return gapfuls[0...keep] unless gapfuls.size < keep
end
end
end
def make_palindrome(front_half, power)
result = front_half
result //= 10 if power.even?
while front_half > 0
result *= 10
result += front_half.remainder(10)
front_half //= 10
end
result
end
t = Time.monotonic
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)}" }
puts (Time.monotonic - t).total_seconds
Here’s the Rust code:
fn palindromicgapfuls(digit: u64, count: u64, keep: usize) -> Vec<u64> {
let mut skipped = 0u64; // initial count of skipped values
let to_skip = count - keep as u64; // count of unwanted values to skip
let mut gapfuls: Vec<u64> = Vec::with_capacity(keep);
let nn = digit * 11; // digit gapful divisor: 11, 22,...88, 99
let (mut power, mut base) = (1, 1u64);
loop {
power += 1;
if power & 1 == 0 { base *= 10 } // value of middle digit position: 10..
let base11 = base * 11; // value of middle two digits positions: 110..
let this_lo = base * digit; // starting half for this digit: 10.. to 90..
let next_lo = base * (digit + 1); // starting half for next digit: 20.. to 100..
for front_half in (this_lo..next_lo).step_by(10) { // d_00; d_10; d_20; ...
let basep = if power & 1 == 1 { base11 } else { base };
let mut palindrome = make_palindrome(front_half, power);
for _ in 0..10 {
if palindrome % nn == 0 {
skipped += 1;
if skipped > to_skip {
gapfuls.push(palindrome);
if gapfuls.len() >= keep { return gapfuls; }
}
};
palindrome += basep;
}
}
}
}
fn make_palindrome(mut front_half: u64, power: u64) -> u64 {
let mut result = front_half;
if power & 1 == 0 { result /= 10; }
while front_half > 0 {
result *= 10;
result += front_half % 10;
front_half /= 10;
}
result
}
fn main() {
let t = std::time::Instant::now();
let (count, keep) = (20, 20);
println!("First 20 palindromic gapful numbers ending with:");
for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }
let (count, keep) = (100, 15);
println!("\nLast 15 of first 100 palindromic gapful numbers ending in:");
for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }
let (count, keep) = (1_000, 10);
println!("\nLast 10 of first 1000 palindromic gapful numbers ending in:");
for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }
let (count, keep) = (100_000, 1);
println!("\n100,000th palindromic gapful number ending with:");
for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }
let (count, keep) = (1_000_000, 1);
println!("\n1,000,000th palindromic gapful number ending with:");
for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }
let (count, keep) = (10_000_000, 1);
println!("\n10,000,000th palindromic gapful number ending with:");
for digit in 1..10 { println!("{} : {:?}", digit, palindromicgapfuls(digit, count, keep)); }
println!("{:?}", t.elapsed())
}