You are given a positive integer
$N.Write a script to generate all Rare numbers of size
$Nif exists. Please checkout the page for more information about it.
(a) 2 digits: 65 (b) 6 digits: 621770 (c) 9 digits: 281089082
If we follow the given link, it turns out that a rare number is a number \(r\) such that \(r + r_v\) and \(r - r_v\) are perfect squares, where \(r_v\) is constructed from \(r\) by reversing its digits. Furthermore, \(r\) should not be a palindrome.
At first glance this looks like an easy exercise; just take all numbers of a specific size, and for each of them, reverse it, take the sum and difference of the original and reversal, and see whether they are perfect square.
But that quickly becomes unwieldy; this is exponential in N, where
N is the given size. As Shyam (the person who named and studied
rare numbers)
writes:
I have developed a computer program in Fortran to calculate Rare
numbers. In fact with refinement of the code over the years, the
program has been made so powerful that all numbers up to \(10^{14}\)
can be just checked for Rare numbers in less than a minute on Pentium
III PC. In few hours I have been able to check up to \(10^{18}\).
Richard Guy writes: Here are three problems that have come to light recently, each of which can consume unlimited amounts of computer time, perhaps without revealing anything significant. One of those three problems is the problem of finding Rare Numbers. (The article is behind a pay wall, but the relevant quote can be seen on the free preview).
Now, modern computers are faster than a Pentium III, but this shows that doing the actual calculations for a Perl Weekly Challenge seems excessive.
The rare numbers are (of course) found on the On-Line Encyclopedia of Integer Sequences®; as sequence A035519. It does show code to check whether a number is a Rare Number, but it doesn't have code to efficiently calculate the Rare Numbers. But it has a list of all known Rare Numbers. And it turns out, only 124 Rare Numbers are known, all of length 22 or less. And this gives us a way of doing the challenge efficiently.
One way of attacking the challenge by including the list of known Rare Numbers, and checking the length all the numbers with the given input.
But since we have the list of numbers, we can do a bit of preprocessing. We can take all the known Rare Numbers, group them by size, join Rare Numbers of the same length by newlines, and put the resulting numbers in an array, indexed by length of the Rare Numbers. Then the resulting program includes this array, and just prints the corresponding entry (if any).
And we can do this for all languages (except BASIC) we solve the challenge with.
We're reading the data from the list of
numbers we found at the
OEIS. This list consists of lines, each line
having an index number (which we will ignore), and a Rare Number.
We have this list available in a file called
rare_numbers.txt.
We start off by reading in the numbers, and putting them in buckets, so all numbers of the same length are in the same bucket:
open my $fh, "<", "rare_numbers.txt" or die "open rare_numbers.txt: $!";
my @buckets;
while (my $rn = <$fh>) {
chomp $rn;
$rn =~ s/^[0-9]+\s+//;
push @{$buckets [length $rn]} => $rn;
}
my @bs = sort {$a <=> $b} grep {$buckets [$_]} keys @buckets;
Now @buckets will have the buckets (each bucket an array of numbers (as strings)), and @bs will contain the indices of the non-empty buckets.
We now open a file for each of the languages we're solving this challenge in:
open my $awk_h, ">", "rn.awk" or die "open rn.awk: $!";
open my $bash_h, ">", "rn.sh" or die "open rn.sh: $!";
open my $basic_h, ">", "rn.bas" or die "open rn.bas: $!";
open my $c_h, ">", "rn.c" or die "open rn.c: $!";
open my $lua_h, ">", "rn.lua" or die "open rn.lua: $!";
open my $node_h, ">", "rn.js" or die "open rn.js: $!";
open my $perl_h, ">", "rn.pl" or die "open rn.pl: $!";
open my $python_h, ">", "rn.py" or die "open rn.py: $!";
open my $ruby_h, ">", "rn.rb" or die "open rn.rb: $!";
We then start off with writing some code declaring arrays:
my $basic_ln = 1000;
say $awk_h "BEGIN {";
say $bash_h "declare -a rare_numbers\n";
say $basic_h "$basic_ln INPUT length\n\n";
say $c_h "char * rare_numbers [23];\n";
say $c_h "int main () {";
say $lua_h "rare_numbers = {}\n";
say $node_h "let rare_numbers = []\n";
say $perl_h "my \@rare_numbers;\n";
say $python_h "rare_numbers = {}\n";
say $ruby_h "rare_numbers = Array . new";
We will now iterate over the buckets, and add write code populating the rare_numbers arrays. If there are multiple Rare Numbers of the same length, we concatenate several strings. Some languages have a concatenate operator (Lua, Node.js, Perl, Python, Ruby), others juxtaposition (AWK, Bash, C).
foreach my $bs (0 .. 22) {
if (!$buckets [$bs]) {
printf $c_h " rare_numbers [%2d] = NULL;\n"
=> $bs;
next;
}
#
# AWK
#
printf $awk_h ' rare_numbers [%2d] = ', $bs;
print $awk_h join " \\\n " =>
map {sprintf "%26s", qq {"$_\\n"}} @{$buckets [$bs]};
print $awk_h "\n";
#
# Bash
#
printf $bash_h 'rare_numbers[%2d]=', $bs;
print $bash_h join "\\\n" =>
map {qq {"$_\\n"}} @{$buckets [$bs]};
print $bash_h "\n";
#
# BASIC
#
for my $rn (@{$buckets [$bs]}) {
printf $basic_h qq "%03d IF length = %2d THEN PRINT %24s\n"
=> ($basic_ln += 10), $bs, qq {"$rn"}
}
#
# C
#
printf $c_h ' rare_numbers [%2d] = ', $bs;
print $c_h join " \\\n " =>
map {sprintf "%26s", qq {"$_\\n"}} @{$buckets [$bs]};
print $c_h ";\n";
#
# Lua
#
printf $lua_h "rare_numbers [%2d] = ", $bs;
print $lua_h join " ..\n " =>
map {sprintf "%26s", qq {"$_\\n"}} @{$buckets [$bs]};
print $lua_h "\n";
#
# Node.js
#
printf $node_h "rare_numbers [%2d] = ", $bs;
print $node_h join " +\n " =>
map {sprintf "%26s", qq {"$_\\n"}} @{$buckets [$bs]};
print $node_h "\n";
#
# Perl
#
printf $perl_h '$rare_numbers [%2d] = ', $bs;
print $perl_h join " .\n " =>
map {sprintf "%26s", qq {"$_\\n"}} @{$buckets [$bs]};
say $perl_h ";";
#
# Python
#
printf $python_h "rare_numbers [%4s] =", "'$bs'";
print $python_h join " +\\\n " =>
map {sprintf "%26s", qq {"$_\\n"}} @{$buckets [$bs]};
print $python_h "\n";
#
# Ruby
#
printf $ruby_h "rare_numbers [%2s] =", $bs;
print $ruby_h join " +\n " =>
map {sprintf "%26s", qq {"$_\\n"}} @{$buckets [$bs]};
print $ruby_h "\n";
}
We can now finish off the files, and close them:
say $awk_h "}";
say $c_h "}";
close $awk_h or die "close rn.awk: $!";
close $bash_h or die "close rn.sh: $!";
close $basic_h or die "close rn.bas: $!";
close $c_h or die "close rn.c: $!";
close $lua_h or die "close rn.lua: $!";
close $node_h or die "close rn.js: $!";
close $perl_h or die "close rn.pl: $!";
close $python_h or die "close rn.py: $!";
close $ruby_h or die "close rn.rb: $!";
Find the complete preprocessing program on GitHub.
We can now use the generated files to create the solutions to the challenge. Unless indicated otherwise, the programs will read input from standard input, with a length on each line of input.
my @rare_numbers;
$rare_numbers [ 2] = "65\n";
$rare_numbers [ 6] = "621770\n";
$rare_numbers [ 9] = "281089082\n";
$rare_numbers [10] = "2022652202\n" .
"2042832002\n";
$rare_numbers [12] = "868591084757\n" .
"872546974178\n" .
"872568754178\n";
#
# ... More entries ...
#
print $rare_numbers [$_] // "" while <>;
Once we have the array with the known Rare Numbers, we just read the require length from standard input, and print the corresponding entry — or the empty string if there are no known Rare Numbers of that length.
Find the full program on GitHub.
BEGIN {
rare_numbers [ 2] = "65\n"
rare_numbers [ 6] = "621770\n"
rare_numbers [ 9] = "281089082\n"
rare_numbers [10] = "2022652202\n" \
"2042832002\n"
rare_numbers [12] = "868591084757\n" \
"872546974178\n" \
"872568754178\n"
#
# ... More entries ...
#
}
{
if ($1 in rare_numbers) {
printf "%s", rare_numbers [$1]
}
}
Once we have the array in place (which is done in a BEGIN block),
we read lengths from standard input (which is available in $1).
If we have an entry for that length, we print it.
Find the full program on GitHub.
declare -a rare_numbers
rare_numbers[ 2]="65\n"
rare_numbers[ 6]="621770\n"
rare_numbers[ 9]="281089082\n"
rare_numbers[10]="2022652202\n"\
"2042832002\n"
rare_numbers[12]="868591084757\n"\
"872546974178\n"\
"872568754178\n"
#
# ... More entries ...
#
while read length
do printf "${rare_numbers[$length]}"
done
Note that in Bash, unlike in AWK or C, juxtaposition only works if there are no spaces in between, hence the absence of indentation. An non-existing entry in an array is equivalent to an empty string, so we don't need to check for existence.
Our BASIC solution is very different. We're using a very bare bones
implementation of BASIC
(Language::Basic),
and it's easier just to have a bunch of IF statements:
1000 INPUT length
1005 IF length < 0 THEN END
1010 IF length = 2 THEN PRINT "65"
1020 IF length = 6 THEN PRINT "621770"
1030 IF length = 9 THEN PRINT "281089082"
1040 IF length = 10 THEN PRINT "2022652202"
1050 IF length = 10 THEN PRINT "2042832002"
1060 IF length = 12 THEN PRINT "868591084757"
1070 IF length = 12 THEN PRINT "872546974178"
1080 IF length = 12 THEN PRINT "872568754178"
3999 REM ... More entries ...
5000 GOTO 1000
Input should be terminated with a line containing a negative number.
Find the full program on GitHub.
In C, we cannot index outside of an array, or deal with uninitialized
values, so we have NULL values for lengths which don't have Rare
Numbers, and check the input so we don't index outside of the array:
# define MAX_RARE_NUMBER_LENGTH 22
char * rare_numbers [MAX_RARE_NUMBER_LENGTH + 1];
int main () {
rare_numbers [ 0] = NULL;
rare_numbers [ 1] = NULL;
rare_numbers [ 2] = "65\n";
rare_numbers [ 3] = NULL;
rare_numbers [ 4] = NULL;
rare_numbers [ 5] = NULL;
rare_numbers [ 6] = "621770\n";
rare_numbers [ 7] = NULL;
rare_numbers [ 8] = NULL;
rare_numbers [ 9] = "281089082\n";
rare_numbers [10] = "2022652202\n" \
"2042832002\n";
rare_numbers [11] = NULL;
rare_numbers [12] = "868591084757\n" \
"872546974178\n" \
"872568754178\n";
/*
* ... More entries ...
*/
int length;
while (scanf ("%d", &length) > 0) {
if (length >= 0 && length <= MAX_RARE_NUMBER_LENGTH &&
rare_numbers [length] != NULL) {
printf ("%s", rare_numbers [length]);
}
}
return (0);
}
Find the full program on GitHub.
The Lua solution is very similar to the Perl one. Lua uses .. to
concatenate strings, and requires an explicit conversion from strings
to numbers:
rare_numbers = {}
rare_numbers [ 2] = "65\n"
rare_numbers [ 6] = "621770\n"
rare_numbers [ 9] = "281089082\n"
rare_numbers [10] = "2022652202\n" ..
"2042832002\n"
rare_numbers [12] = "868591084757\n" ..
"872546974178\n" ..
"872568754178\n"
--
-- ... More entries ...
--
for length in io . lines () do
length = tonumber (length)
if rare_numbers [length]
then io . write (rare_numbers [length])
end
end
Find the full program on GitHub.
Our solution in Node.js is also similar to the Perl one. Unary +
converts a string to a number, while binary + can be used to
concatenate strings:
let rare_numbers = []
rare_numbers [ 2] = "65\n"
rare_numbers [ 6] = "621770\n"
rare_numbers [ 9] = "281089082\n"
rare_numbers [10] = "2022652202\n" +
"2042832002\n"
rare_numbers [12] = "868591084757\n" +
"872546974178\n" +
"872568754178\n"
//
// ... More entries ...
//
require ('readline')
. createInterface ({input: process . stdin})
. on ('line', _ => process . stdout . write (rare_numbers [+_] || ""))
;
Find the full program on GitHub.
Something similar in Python as well. But here we're using a dictionary (which uses strings to index) to store the Rare Numbers, so we can more easily check whether there is an entry:
rare_numbers = {}
rare_numbers [ '2'] = "65\n"
rare_numbers [ '6'] = "621770\n"
rare_numbers [ '9'] = "281089082\n"
rare_numbers ['10'] = "2022652202\n" +\
"2042832002\n"
rare_numbers ['12'] = "868591084757\n" +\
"872546974178\n" +\
"872568754178\n"
#
# ... More entries ...
#
for l in fileinput . input ():
l = l . strip ()
if l in rare_numbers:
sys . stdout . write (rare_numbers [l])
Find the full program on GitHub.
And the solution in Ruby is similar as well, using + to concatenate
strings, and the to_i method to convert a string to an integer:
rare_numbers = Array . new
rare_numbers [ 2] = "65\n"
rare_numbers [ 6] = "621770\n"
rare_numbers [ 9] = "281089082\n"
rare_numbers [10] = "2022652202\n" +
"2042832002\n"
rare_numbers [12] = "868591084757\n" +
"872546974178\n" +
"872568754178\n"
#
# ... More entries ...
#
ARGF . each_line do |length|
print rare_numbers [length . to_i]
end
Find the full program on GitHub.