Rare numbers
Translation of Rust
# 20220315 Raku programming solution
sub rare (\target where ( target > 0 and target ~~ Int )) {
my \digit = $ = 2;
my $count = 0;
my @numeric_digits = 0..9 Z, 0 xx *;
my @diffs1 = 0,1,4,5,6;
# all possible digits pairs to calculate potential diffs
my @pairs = 0..9 X 0..9;
my @all_diffs = -9..9;
# lookup table for the first diff
my @lookup_1 = [ [[2, 2], [8, 8]], # Diff = 0
[[8, 7], [6, 5]], # Diff = 1
[],
[],
[[4, 0], ], # Diff = 4
[[8, 3], ], # Diff = 5
[[6, 0], [8, 2]], ]; # Diff = 6
# lookup table for all the remaining diffs
given my %lookup_n { for @pairs -> \pair { $_{ [-] pair.values }.push: pair } }
loop {
my @powers = 10 <<**<< (0..digit-1); # powers like 1, 10, 100, 1000....
# for n-r (aka L) the required terms, like 9/ 99 / 999 & 90 / 99999 & 9999 & 900 etc
my @terms = (@powers.reverse Z- @powers).grep: * > 0 ;
# create a cartesian product for all potential diff numbers
# for the first use the very short one, for all other the complete 19 element
my @diff_list = digit == 2 ?? @diffs1 !! [X] @diffs1, |(@all_diffs xx digit div 2 - 1);
my @diff_list_iter = gather for @diff_list -> \k {
# remove invalid first diff/second diff combinations
{ take k andthen next } if k.elems == 1 ;
given (my (\a,\b) = k.values) {
when a == 0 && b != 0 { next }
when a == 1 && b ∉ [ -7, -5, -3, -1, 1, 3, 5, 7 ] { next }
when a == 4 && b ∉ [ -8, -6, -4, -2, 0, 2, 4, 6, 8 ] { next }
when a == 5 && b ∉ [ -3, 7 ] { next }
when a == 6 && b ∉ [ -9, -7, -5, -3, -1, 1, 3, 5, 7, 9 ] { next }
default { take k }
}
}
for @diff_list_iter -> \diffs {
# calculate difference of original n and its reverse (aka L = n-r)
# which must be a perfect square
if (my \L = [+] diffs <<*>> @terms) > 0 and { $_ == $_.Int }(L.sqrt) {
# potential candiate, at least L is a perfect square
# placeholder for the digits
my \dig = @ = 0 xx digit;
# generate a cartesian product for each identified diff using the lookup tables
my @c_iter = digit == 2
?? @lookup_1[diffs[0]].map: { [ $_ ] }
!! [X] @lookup_1[diffs[0]], |(1..(+diffs + (digit % 2 - 1))).map: -> \k {
k == diffs ?? @numeric_digits !! %lookup_n{diffs[k]} }
# check each H (n+r) by using digit combination
for @c_iter -> \elt {
for elt.kv -> \i, \pair { dig[i,digit-1-i] = pair.values }
# for numbers with odd # digits restore the middle digit
# which has been overwritten at the end of the previous cycle
dig[(digit - 1) div 2] = elt[+elt - 1][0] if digit % 2 == 1 ;
my \rev = ( my \num = [~] dig ).flip;
if num > rev and { $_ == $_.Int }((num+rev).sqrt) {
printf "%d: %12d reverse %d\n", $count+1, num, rev;
exit if ++$count == target;
}
}
}
}
digit++
}
}
my $N = 5;
say "The first $N rare numbers are,";
rare $N;Output:
The first 5 rare numbers are,
1: 65 reverse 56
2: 621770 reverse 77126
3: 281089082 reverse 280980182
4: 2022652202 reverse 2022562202
5: 2042832002 reverse 2002382402Using NativeCall with Rust
This example will make use of a modified version of the 'advanced' routine from the Rust entry.
~> cargo new --lib Rare && cd $_
Created library `Rare` packageAdd to the stock manifest file, Cargo.toml, all required dependencies and build target,
~/Rare> tail -5 Cargo.toml
[dependencies]
itertools = "0.10.3"
[lib]
crate-type = ["cdylib"]Now replace the src/lib.rs file with the following,
lib.rs
use itertools::Itertools;
use std::collections::HashMap;
fn isqrt(n: u64) -> u64 {
let mut s = (n as f64).sqrt() as u64;
s = (s + n / s) >> 1;
if s * s > n {
s - 1
} else {
s
}
}
fn is_square(n: u64) -> bool {
match n & 0xf {
0 | 1 | 4 | 9 => {
let t = isqrt(n);
t * t == n
}
_ => false,
}
}
#[no_mangle]
/// This algorithm uses an advanced search strategy based on Nigel Galloway's approach
pub extern "C" fn advanced64(target: u8) -> *mut u64 {
// setup
let digit = 2u8;
let mut results = Vec::new();
let mut counter = 0_u8;
let numeric_digits = (0..=9).map(|x| [x, 0]).collect::<Vec<_>>();
let diffs1: Vec<i8> = vec![0, 1, 4, 5, 6];
// all possible digits pairs to calculate potential diffs
let pairs = (0_i8..=9)
.cartesian_product(0_i8..=9)
.map(|x| [x.0, x.1])
.collect::<Vec<_>>();
let all_diffs = (-9i8..=9).collect::<Vec<_>>();
// lookup table for the first diff
let lookup_1 = vec![
vec![[2, 2], [8, 8]], //Diff = 0
vec![[8, 7], [6, 5]], //Diff = 1
vec![],
vec![],
vec![[4, 0]], // Diff = 4
vec![[8, 3]], // Diff = 5
vec![[6, 0], [8, 2]], // Diff = 6
];
// lookup table for all the remaining diffs
let lookup_n: HashMap<i8, Vec<_>> = pairs.into_iter().into_group_map_by(|elt| elt[0] - elt[1]);
let mut d = digit;
while target > counter {
// powers like 1, 10, 100, 1000....
let powers = (0..d).map(|x| 10_u64.pow(x.into())).collect::<Vec<u64>>();
// for n-r (aka L) the required terms, like 9/ 99 / 999 & 90 / 99999 & 9999 & 900 etc
let terms = powers
.iter()
.zip(powers.iter().rev())
.map(|(a, b)| b.checked_sub(*a).unwrap_or(0))
.filter(|x| *x != 0)
.collect::<Vec<u64>>();
// create a cartesian product for all potential diff numbers
// for the first use the very short one, for all other the complete 19 element
let diff_list_iter = (0_u8..(d / 2))
.map(|i| match i {
0 => diffs1.iter(),
_ => all_diffs.iter(),
})
.multi_cartesian_product()
// remove invalid first diff/second diff combinations - custom iterator would be probably better
.filter(|x| {
if x.len() == 1 {
return true;
}
match (*x[0], *x[1]) {
(a, b) if (a == 0 && b != 0) => false,
(a, b) if (a == 1 && ![-7, -5, -3, -1, 1, 3, 5, 7].contains(&b)) => false,
(a, b) if (a == 4 && ![-8, -6, -4, -2, 0, 2, 4, 6, 8].contains(&b)) => false,
(a, b) if (a == 5 && ![7, -3].contains(&b)) => false,
(a, b) if (a == 6 && ![-9, -7, -5, -3, -1, 1, 3, 5, 7, 9].contains(&b)) => {
false
}
_ => true,
}
});
'OUTER: for diffs in diff_list_iter {
// calculate difference of original n and its reverse (aka L = n-r)
// which must be a perfect square
let l: i64 = diffs
.iter()
.zip(terms.iter())
.map(|(diff, term)| **diff as i64 * *term as i64)
.sum();
if l > 0 && is_square(l.try_into().unwrap()) {
// potential candiate, at least L is a perfect square
// placeholder for the digits
let mut dig: Vec<i8> = vec![0_i8; d.into()];
// generate a cartesian product for each identified diff using the lookup tables
let c_iter = (0..(diffs.len() + d as usize % 2))
.map(|i| match i {
0 => lookup_1[*diffs[0] as usize].iter(),
_ if i != diffs.len() => lookup_n.get(diffs[i]).unwrap().iter(),
_ => numeric_digits.iter(), // for the middle digits
})
.multi_cartesian_product();
// check each H (n+r) by using digit combination
c_iter.for_each(|elt| {
for (i, digit_pair) in elt.iter().enumerate() {
dig[i] = digit_pair[0];
dig[d as usize - 1 - i] = digit_pair[1]
}
// for numbers with odd # digits restore the middle digit
// which has been overwritten at the end of the previous cycle
if d % 2 == 1 {
dig[(d as usize - 1) / 2] = elt[elt.len() - 1][0];
}
let num = dig
.iter()
.rev()
.enumerate()
.fold(0_u64, |acc, (i, d)| acc + 10_u64.pow(i as u32) * *d as u64);
let reverse = dig
.iter()
.enumerate()
.fold(0_u64, |acc, (i, d)| acc + 10_u64.pow(i as u32) * *d as u64);
if num > reverse && is_square(num + reverse) {
counter += 1;
results.push(num);
}
});
if counter == target {
break 'OUTER;
}
}
}
d += 1
}
let ptr = results.as_mut_ptr();
std::mem::forget(results); // circumvent the destructor
ptr
}The needful shared library will be available after the build command,
~/Rare> cargo build
~/Rare> file target/debug/libRare.so
target/debug/libRare.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, BuildID[sha1]=4f904cce7f8e82130826bf46f93fe9fe944ab9d0, with debug_info, not strippedHere is the main Raku program,
use NativeCall;
constant LIB = '/home/hkdtam/Rare/target/debug/libRare.so';
sub advanced64(uint8) returns Pointer[uint64] is native(LIB) {*}
my $N = 5;
say "The first $N rare numbers are,";
for (advanced64 $N)[^$N].kv -> \nth,\rare {
printf "%d: %12d reverse %d\n", nth+1, { $_, $_.flip }(rare)
}Output is the same.
Last updated