Upside-down numbers

You are encouraged to solve this task according to the task description, using any language you may know.
An upside-down number is a positive base 10 integer whose i-th leftmost and i-th rightmost digits are complements, i.e., their sum is 10.
- For example
7165493 is an upside-down number. 7 + 3 = 10 1 + 9 = 10 6 + 4 = 10 5 + 5 = 10
From that definition it follows that an upside-down number cannot contain any zeros, and if there is an odd number of digits, then the center digit must be a 5.
- Task
- Write a routine to find (or generate) upside-down numbers.
- Find and show the first 50 upside-down numbers.
- Find and show the five hundredth upside-down number.
- Find and show the five thousandth upside-down number.
- Stretch
- Find and show the fifty thousandth, five hundred thousandth, five millionth upside-down number.
- See also
Ada
Version 1 (slower, direct from definition)
pragma Ada_2022;
with Ada.Text_IO;
with Ada.Containers.Indefinite_Vectors;
with Ada.Containers.Indefinite_Ordered_Sets;
procedure Upside_Down_Numbers is
-- a rather slow algorithm that proceeds by recursive expansion; i.e.,
-- a straightforward implementation via the definition
package IO renames Ada.Text_IO;
subtype Digit is Integer range 1 .. 9;
Mirror : constant array (Digit) of Digit :=
[for Ith in Digit => 10 - Ith];
type Upside_Down_Number is array (Positive range <>) of Digit;
procedure Put (Number : Upside_Down_Number) is
package Digit_IO is new IO.Integer_IO (Num => Digit);
begin
for N of Number loop
Digit_IO.Put (N, 0);
end loop;
end Put;
package Upside_Down_Vecs is new Ada.Containers.Indefinite_Vectors
(Index_Type => Positive, Element_Type => Upside_Down_Number);
subtype Upside_Down_Vec is Upside_Down_Vecs.Vector;
package Upside_Down_Sets is new Ada.Containers.Indefinite_Ordered_Sets
(Element_Type => Upside_Down_Number);
subtype Upside_Down_Set is Upside_Down_Sets.Set;
function Expand_Even (Numbers : Upside_Down_Set) return Upside_Down_Set is
-- if Numbers holds even-length upside-down numbers,
-- this expands them to corresponding odd-length upside-down numbers
Result : Upside_Down_Set;
Length : constant Positive := Numbers.First_Element'Length;
Half_Length : constant Positive := Length / 2;
New_Number : Upside_Down_Number (1 .. Length + 1);
begin
for Old_Number of Numbers loop
for Ith in 1 .. Half_Length loop
New_Number (Ith) := Old_Number (Ith);
New_Number (Length + 1 - Ith + 1) := Old_Number (Length - Ith + 1);
end loop;
New_Number (Half_Length + 1) := 5;
if not Result.Contains (New_Number) then
Result.Insert (New_Number);
end if;
end loop;
return Result;
end Expand_Even;
function Expand_Odd (Numbers : Upside_Down_Set) return Upside_Down_Set is
-- if Numbers holds odd-length upside-down numbers,
-- this expands them to corresponding even-length upside-down numbers
--
-- alas, this is inefficient not only by exhaustive enumeration,
-- but by generating several numbers more than once
Result : Upside_Down_Set;
Length : constant Positive := Numbers.First_Element'Length;
Half_Length : constant Positive := (Length + 1) / 2;
New_Number : Upside_Down_Number (1 .. Length + 1);
begin
for Old_Number of Numbers loop
for Breakpoint in 1 .. Half_Length loop
for Ith in 1 .. Half_Length loop
if Ith < Breakpoint then
New_Number (Ith) := Old_Number (Ith);
New_Number (Length + 1 - Ith + 1) :=
Old_Number (Length - Ith + 1);
elsif Ith >= Breakpoint then
New_Number (Ith + 1) := Old_Number (Ith);
New_Number (Length + 1 - Ith) :=
Old_Number (Length - Ith + 1);
end if;
end loop;
for D in Digit loop
New_Number (Breakpoint) := D;
New_Number (Length + 1 - Breakpoint + 1) := Mirror (D);
if not Result.Contains (New_Number) then
Result.Insert (New_Number);
end if;
end loop;
end loop;
end loop;
return Result;
end Expand_Odd;
function Expand (Number : Upside_Down_Set) return Upside_Down_Set is
(if Number.First_Element'Length mod 2 = 0 then Expand_Even (Number)
else Expand_Odd (Number));
Iterations : array (1 .. 100) of Upside_Down_Set;
Result : Upside_Down_Vec;
Number_Computed : Positive := 1;
Ith : Positive := 1;
begin
IO.Put_Line ("Slow Formula");
IO.Put_Line ("==== =======");
Iterations (1).Insert (Upside_Down_Number'[5]);
Result.Append (Upside_Down_Number'[5]);
while Number_Computed < 5_000_000 loop
Iterations (Ith + 1) := Expand (Iterations (Ith));
Number_Computed := @ + Positive (Iterations (Ith + 1).Length);
for Each of Iterations (Ith + 1) loop
Result.Append (Each);
end loop;
Ith := @ + 1;
end loop;
IO.Put_Line ("Computed" & Number_Computed'Image & " upside-down numbers");
IO.Put ("The first 50: ");
for Ith in 1 .. 50 loop
Put (Result (Ith));
IO.Put (", ");
end loop;
IO.New_Line;
IO.Put ("The 500th: ");
Put (Result (500));
IO.New_Line;
IO.Put ("The 5_000th: ");
Put (Result (5_000));
IO.New_Line;
IO.Put ("The 500_000th: ");
Put (Result (500_000));
IO.New_Line;
IO.Put ("The 5_000_000th: ");
Put (Result (5_000_000));
IO.New_Line;
end Upside_Down_Numbers;
- Output:
Slow Formula ==== ======= Computed 5978710 upside-down numbers The first 50: 5, 19, 28, 37, 46, 55, 64, 73, 82, 91, 159, 258, 357, 456, 555, 654, 753, 852, 951, 1199, 1289, 1379, 1469, 1559, 1649, 1739, 1829, 1919, 2198, 2288, 2378, 2468, 2558, 2648, 2738, 2828, 2918, 3197, 3287, 3377, 3467, 3557, 3647, 3737, 3827, 3917, 4196, 4286, 4376, 4466, The 500th: 494616 The 5_000th: 56546545 The 500_000th: 729664644183 The 5_000_000th: 82485246852682
Version 2
pragma Ada_2022;
with Ada.Text_IO;
with Ada.Containers.Indefinite_Vectors;
with Ada.Containers.Indefinite_Ordered_Sets;
procedure Upside_Down_Numbers is
-- This translates the Phix solution, which essentially puts in a formula
-- the roughly quadratic growth of the upside-down numbers.
-- The essential insight is that every even digit increases
-- the number of new numbers generated by a factor of 10.
-- So, there are only 1 upside-down number of length 1,
-- 9 of length 2, 9 of length 3, 81 of length 4, and so forth.
-- From this fact you can navigate your way relatively quickly
-- to the desired number.
package IO renames Ada.Text_IO;
subtype Digit is Integer range 1 .. 9;
Mirror : constant array (Digit) of Digit :=
[for Ith in Digit => 10 - Ith];
type Upside_Down_Number is array (Positive range <>) of Digit;
procedure Put (Number : Upside_Down_Number) is
package Digit_IO is new IO.Integer_IO (Num => Digit);
begin
for N of Number loop
Digit_IO.Put (N, 0);
end loop;
end Put;
function Kth_Of_N (Kth, Digit, Count : Natural) return Upside_Down_Number is
-- we want the Kth integer of Digit length,
-- when we know it is Count from the first of this length
New_Count : Natural := Count;
New_Kth : Natural := Kth;
This_Digit : Natural;
begin
if Digit = 0 then
return Upside_Down_Number'[];
elsif Digit = 1 then
return Upside_Down_Number'[5];
else
New_Count := @ / 9;
This_Digit := (New_Kth - 1) / New_Count + 1;
New_Kth := @ - (This_Digit - 1) * New_Count;
declare
Temp : Upside_Down_Number :=
Kth_Of_N (New_Kth, Digit - 2, New_Count);
Result : Upside_Down_Number (1 .. Temp'Length + 2) :=
[1 => This_Digit, others => 1];
begin
Result (Temp'Last + 2) := Mirror (This_Digit);
for Ith in Temp'Range loop
Result (Ith + 1) := Temp (Ith);
end loop;
return Result;
end;
end if;
end Kth_Of_N;
function Phormula (Nth : Positive) return Upside_Down_Number is
-- Find the setup for Nth so that the Kth_Of_N formula works out.
-- This implements the insight mentioned above, that
-- the number of upside-down numbers increases by a factor of 9
-- for every even digit.
Digit : Positive := 1; -- number of digits needed
Count : Positive := 1; -- how many we've skipped so far
First : Positive := 1; -- the first u-d number for the current #digits
Last : Positive := 1; -- the last u-d number for the current #digits
begin
while Nth > Last loop
First := Last + 1;
Digit := @ + 1;
if Digit mod 2 = 0 then
Count := @ * 9;
end if;
Last := First + Count - 1;
end loop;
return Kth_Of_N (Nth - First + 1, Digit, Count);
end Phormula;
begin
IO.Put_Line ("Phast Phormula:");
IO.Put_Line ("===== ========");
IO.Put ("The first 50: ");
for Ith in 1 .. 50 loop
Put (Phormula (Ith));
IO.Put (", ");
end loop;
IO.New_Line;
IO.Put ("The 500th: ");
Put (Phormula (500));
IO.New_Line;
IO.Put ("The 5_000th: ");
Put (Phormula (5_000));
IO.New_Line;
IO.Put ("The 500_000th: ");
Put (Phormula (500_000));
IO.New_Line;
IO.Put ("The 5_000_000th: ");
Put (Phormula (5_000_000));
IO.New_Line;
end Upside_Down_Numbers;
- Output:
Phast Phormula: ===== ======== The first 50: 5, 19, 28, 37, 46, 55, 64, 73, 82, 91, 159, 258, 357, 456, 555, 654, 753, 852, 951, 1199, 1289, 1379, 1469, 1559, 1649, 1739, 1829, 1919, 2198, 2288, 2378, 2468, 2558, 2648, 2738, 2828, 2918, 3197, 3287, 3377, 3467, 3557, 3647, 3737, 3827, 3917, 4196, 4286, 4376, 4466, The 500th: 494616 The 5_000th: 56546545 The 500_000th: 729664644183 The 5_000_000th: 82485246852682
ALGOL 68
Assumes LONG INT
is at least 64 bits.
BEGIN # find and count upside-down numbers - translation of Phix #
PROC get counts = ( INT d, REF LONG INT first, last )LONG INT:
BEGIN
LONG INT count := first := last := 1;
FOR i FROM 2 TO d DO
first := last + 1;
IF NOT ODD i THEN count *:= 9 FI;
last := first + count - 1
OD;
count
END # get counts # ;
PROC kth of n = ( LONG INT kth, digits, count )STRING:
IF digits = 0 THEN ""
ELIF digits = 1 THEN "5"
ELSE
OP D = ( INT n )CHAR: REPR ( ABS "0" + n );
LONG INT reduced count := count OVER 9;
INT d = SHORTEN ( ( kth - 1 ) OVER reduced count );
D ( 1 + d ) + kth of n( kth - ( d * reduced count ), digits - 2, reduced count ) + D ( 9 - d )
FI # kth of n # ;
PROC get which = ( LONG INT nth in, REF LONG INT count, first, last, kth, digits )STRING:
BEGIN
LONG INT nth := nth in;
digits := count := first := last := 1;
WHILE nth > last DO
first := last + 1;
digits +:= 1;
IF NOT ODD digits THEN count *:= 9 FI;
last := first + count - 1
OD;
kth := nth - first + 1;
kth of n( kth, digits, count )
END # get which # ;
PROC ord = ( LONG INT n )STRING:
IF INT d2 = SHORTEN ( n MOD 100 );
d2 >= 10 AND d2 <= 20
THEN "th"
ELSE CASE SHORTEN ( n MOD 10 ) IN "st", "nd", "rd" OUT "th" ESAC
FI # ord # ;
print( ( "The first 50 upside down numbers:", newline ) );
FOR i TO 50 DO
STRING ud := get which( i
, LOC LONG INT, LOC LONG INT, LOC LONG INT
, LOC LONG INT, LOC LONG INT
);
WHILE ( UPB ud - LWB ud ) < 3 DO " " +=: ud OD;
print( ( ud, IF i MOD 10 /= 0 THEN " " ELSE newline FI ) )
OD;
print( ( newline ) );
FOR d TO 7 DO
LONG INT first := 0, last := 0;
LONG INT count = get counts( d, first, last );
print( ( "There are ", whole( count, 0 ), " ", whole( d, 0 )
, "-digit upside down numbers (the "
, whole( first, 0 ), ord( first ), " to ", whole( last, 0 ), ord( last )
, ")", newline
)
)
OD;
print( ( "(etc...)", newline, newline ) );
[]LONG INT position = ( 1, 2, 10, 11, 182, 500, 910, 911
, 5 000, 50 000, 500 000, 5 000 000, 50 000 000
, 500 000 000, 5 000 000 000, 50 000 000 000, 500 000 000 000
, 5 000 000 000 000, 50 000 000 000 000, 500 000 000 000 000
, 5 000 000 000 000 000
);
FOR i FROM LWB position TO UPB position DO
LONG INT w = position[ i ];
LONG INT count := 0, first := 0, last := 0, kth := 0, digits := 0;
STRING res = get which( w, count, first, last, kth, digits );
print( ( "The ", whole( w, 0 ), ord( w ), " upside down number"
, " is the ", whole( kth, 0 ), ord( kth ), " ", whole( digits, 0 )
, "-digit number (", res, ")", newline
)
)
OD
END
- Output:
The first 50 upside down numbers: 5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 There are 1 1-digit upside down numbers (the 1st to 1st) There are 9 2-digit upside down numbers (the 2nd to 10th) There are 9 3-digit upside down numbers (the 11th to 19th) There are 81 4-digit upside down numbers (the 20th to 100th) There are 81 5-digit upside down numbers (the 101st to 181st) There are 729 6-digit upside down numbers (the 182nd to 910th) There are 729 7-digit upside down numbers (the 911th to 1639th) (etc...) The 1st upside down number is the 1st 1-digit number (5) The 2nd upside down number is the 1st 2-digit number (19) The 10th upside down number is the 9th 2-digit number (91) The 11th upside down number is the 1st 3-digit number (159) The 182nd upside down number is the 1st 6-digit number (111999) The 500th upside down number is the 319th 6-digit number (494616) The 910th upside down number is the 729th 6-digit number (999111) The 911th upside down number is the 1st 7-digit number (1115999) The 5000th upside down number is the 3361st 8-digit number (56546545) The 50000th upside down number is the 35239th 10-digit number (6441469664) The 500000th upside down number is the 367141st 12-digit number (729664644183) The 5000000th upside down number is the 3804259th 14-digit number (82485246852682) The 50000000th upside down number is the 39238321st 16-digit number (9285587463255281) The 500000000th upside down number is the 15724390th 19-digit number (1436368345672474769) The 5000000000th upside down number is the 641519500th 21-digit number (269222738456273888148) The 50000000000th upside down number is the 10773675490th 23-digit number (41835623444566678457296) The 500000000000th upside down number is the 146963079400th 25-digit number (5724139689945611241796835) The 5000000000000th upside down number is the 1822667714590th 27-digit number (751766588225456588225443953) The 50000000000000th upside down number is the 21404009431300th 29-digit number (94816546925914569158146549261) The 500000000000000th upside down number is the 36744952787041st 32-digit number (12651942383972646483172786195489) The 5000000000000000th upside down number is the 830704575083359th 34-digit number (1513835774459212468981566335727959)
Basic
Applesoft BASIC
Beyond 9 digits, rounding errors occur.
1 PRINT "THE FIRST 50 UPSIDE DOWN NUMBERS:": FOR I = 1 TO 50: GOSUB 4: NEXT I: PRINT
2 FOR J = 2 TO 10::I = INT (5 * 10 ^ J): PRINT CHR$ (13)I"TH: ";: GOSUB 4: NEXT J
3 END
4 GOSUB 5: PRINT O$;: RETURN
5 IF I > = 1E9 THEN PRINT "?OVERFLOW" + CHR$ (7): END
6 L$ = "":R$ = "":S = I - 1:F = 1:I$(1) = "5": FOR E = 0 TO 1E38: FOR O = F TO 1:R = S:S = S - INT (9 ^ E):F = 0: IF S > = 0 THEN NEXT O,E
7 IF E THEN R = R + .5: FOR D = E - 1 TO 0 STEP - 1:N = INT (R / 9 ^ D):L$ = L$ + STR$ (N + 1):R$ = STR$ (9 - N) + R$:R = R - N * INT (9 ^ D): NEXT D
8 O$ = L$ + I$(O) + R$ + " "
9 RETURN
- Output:
THE FIRST 50 UPSIDE DOWN NUMBERS: 5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 500TH: 494616 5000TH: 56546545 50000TH: 6441469664 500000TH: 729664644183 5000000TH: 82485246852682 50000000TH: 9285587463255281 500000000TH: 1436368345672474769 5E+09TH: ?OVERFLOW
FreeBASIC
function is_ups( n as uinteger ) as boolean
dim as string m = str(n)
dim as uinteger lm = len(m), i
for i = 1 to int(lm/2.0+0.5)
if val(mid(m,i,1)) + val(mid(m,lm-i+1,1)) <> 10 then return false
next i
return true
end function
dim as uinteger count, n=0
while count<5000001
if is_ups(n) then
count = count + 1
if count < 51 then
print n,
if count mod 5 = 0 then print
end if
if count = 500 or count = 5000 then
print n
end if
end if
n = n + 1
wend
5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 494616 56546545
C++
#include <iostream>
#include <vector>
#include <algorithm>
bool isUpsideDown( int n ) {
std::vector<int> digits ;
while ( n != 0 ) {
digits.push_back( n % 10 ) ;
n /= 10 ;
}
if ( std::find ( digits.begin( ) , digits.end( ) , 0 ) != digits.end( ) )
return false ;
int forward = 0 ;
int backward = digits.size( ) - 1 ;
while ( forward <= backward ) {
if ( digits[forward] + digits[backward] != 10 )
return false ;
forward++ ;
if ( backward > 0 ) {
backward-- ;
}
}
return true ;
}
int main( ) {
int current = 0 ;
int sum = 0 ;
std::vector<int> solution ;
while ( sum != 5000 ) {
current++ ;
if ( isUpsideDown( current ) ) {
solution.push_back( current ) ;
sum++ ;
}
}
std::cout << "The first 50 upside-down numbers:\n" ;
std::cout << "(" ;
for ( int i = 0 ; i < 50 ; i++ )
std::cout << solution[ i ] << ' ' ;
std::cout << ")\n" ;
std::cout << "The five hundredth such number: " << solution[499] << '\n' ;
std::cout << "The five thousandth such number: " << solution[4999] << '\n' ;
return 0 ;
}
- Output:
The first 50 upside-down numbers: (5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 ) The five hundredth such number: 494616 The five thousandth such number: 56546545
Delphi
function IsUpsideDown(N: integer): boolean;
{Test if N is upsidedown number}
var I,J: integer;
var IA: TIntegerDynArray;
begin
Result:=False;
{Get all digits in the number}
GetDigits(N,IA);
for I:=0 to Length(IA) div 2 do
begin
{Index to right side of number}
J:=High(IA)-I;
{do left and right side add up to 10?}
if IA[J]+IA[I]<>10 then exit;
{No zeros allowed}
if (IA[J]=0) or (IA[I]=0) then exit;
end;
Result:=True;
end;
procedure ShowUpsideDownNumbers(Memo: TMemo);
var I,J,K: integer;
var Cnt: integer;
var S: string;
begin
Cnt:=0;
S:='';
{Show first 50 upside down numbers}
for I:=5 to high(integer) do
if IsUpsideDown(I) then
begin
Inc(Cnt);
S:=S+Format('%5d',[I]);
if (Cnt mod 10)=0 then S:=S+CRLF;
if Cnt=50 then break;
end;
Memo.Lines.Add(S);
{Show 500th, and 5,000th }
for I:=I to high(integer) do
if IsUpsideDown(I) then
begin
Inc(Cnt);
case Cnt of
500: Memo.Lines.Add(Format(' 500th Upsidedown = %10.0n',[I+0.0]));
5000: Memo.Lines.Add(Format('5,000th Upsidedown = %10.0n',[I+0.0]));
end;
if Cnt>5000 then break;
end;
end;
- Output:
5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 500th Upsidedown = 493,716 5,000th Upsidedown = 56,537,545 Elapsed Time: 10.141 Sec.
F#
// Upside-down numbers. Nigel Galloway: September 2nd., 2024
let rec f9 n g l=if n=0I then g else let a,b=bigint.DivRem(n,9I) in f9 a (g+b*10I**l) (l+1)
let fD i=let rec fG n g=let t=g+9I**(n/2) in if t>i then(n,f9 (i-g-1I) 0I 0 + (10I**(n/2)-1I)/9I) else fG (n+1) t in fG 1 0I
let rec fN n g=if n=0I then g else let a,b=bigint.DivRem(n,10I) in fN a (g*10I+10I-b)
let fG n g=let i=fN g 0I in if n%2=0 then g*10I**(n/2)+i else (g*10I+5I)*10I**(n/2)+i
let udn n=match fD n with _,n when n=0I->5I |n,g when g%10I=0I->fG n (10I**((n-1)/2)-1I) |n,g->fG n g
[1I..50I]|>Seq.iter(udn>>printf "%A "); printfn "\n"
[182I;500I;910I;911I]|>Seq.iter(fun n->printfn "%A -> %A" n (udn n)); printfn ""
Seq.unfold(fun n->Some(n,n*10I))5000I|>Seq.take 13|>Seq.iter(fun n->printfn "%A -> %A" n (udn n)); printfn ""
let n=10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001I in printfn "I suppose I must\n%A -> %A" n (udn n)
- Output:
5 19 28 37 46 55 64 73 82 5 159 258 357 456 555 654 753 852 901 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 182 -> 111999 500 -> 494616 910 -> 9995111 911 -> 1115999 5000 -> 56546545 50000 -> 6441469664 500000 -> 729664644183 5000000 -> 82485246852682 50000000 -> 9285587463255281 500000000 -> 1436368345672474769 5000000000 -> 269222738456273888148 50000000000 -> 41835623444566678457296 500000000000 -> 5724139689945611241796835 5000000000000 -> 751766588225456588225443953 50000000000000 -> 94816546925914569158146549261 500000000000000 -> 12651942383972646483172786195489 5000000000000000 -> 1513835774459212468981566335727959 I suppose I must 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 -> 454594394343883179243759282183821923122343988685136868482218367266879951778395152999458916423484426556991911455486626786491256111859517233951132448347298826242479524221767889781982729828153768139722767617615656
FutureBasic
_max = 50000000 // 10^n * 5 : n < 8
void local fn upsideDown
static uint64 list(_max)
uint64 i, j, add, strt = 0, ndx = 0, qty = 1, m1_9 = 1
uint64 count = 2, mag = 10, tgt = 500
list(0) = 0 : list(1) = 5
print @"\n\tFirst 50 upside-down numbers:\n 5";
while 1
add = mag + 9
for i = 1 to 9
ndx = strt
for j = 1 to qty
list(count) = list(ndx) * 10 + add
if count <= 50
printf @"%7lu\b", list(count)
if count mod 10 == 0 then print
else
if count == tgt
printf @"\n%20luth upside-down number is %lu\b", tgt, list(count)
if tgt >= _max then exit fn
tgt *= 10
end if
end if
count++
ndx++
next
add += mag -1
next
strt = ndx
mag *= 10
qty *= m1_9
m1_9 = m1_9 xor 8 // Toggles between 1 and 9
wend
end fn
window 1, @"Upside-down Numbers"
CFTimeInterval t : t = fn CACurrentMediaTime
fn upsideDown
printf @"\n\n\tExecution time: %.3f sec.",1*(fn CACurrentMediaTime - t)
HandleEvents
- Output:
Go
package main
import (
"fmt"
"rcu"
)
func genUpsideDown(limit int) chan int {
ch := make(chan int)
wrappings := [][2]int{
{1, 9}, {2, 8}, {3, 7}, {4, 6}, {5, 5},
{6, 4}, {7, 3}, {8, 2}, {9, 1},
}
evens := []int{19, 28, 37, 46, 55, 64, 73, 82, 91}
odds := []int{5}
oddIndex := 0
evenIndex := 0
ndigits := 1
pow := 100
count := 0
go func() {
for count < limit {
if ndigits%2 == 1 {
if len(odds) > oddIndex {
ch <- odds[oddIndex]
count++
oddIndex++
} else {
// build next odds, but switch to evens
var nextOdds []int
for _, w := range wrappings {
for _, i := range odds {
nextOdds = append(nextOdds, w[0]*pow+i*10+w[1])
}
}
odds = nextOdds
ndigits++
pow *= 10
oddIndex = 0
}
} else {
if len(evens) > evenIndex {
ch <- evens[evenIndex]
count++
evenIndex++
} else {
// build next evens, but switch to odds
var nextEvens []int
for _, w := range wrappings {
for _, i := range evens {
nextEvens = append(nextEvens, w[0]*pow+i*10+w[1])
}
}
evens = nextEvens
ndigits++
pow *= 10
evenIndex = 0
}
}
}
close(ch)
}()
return ch
}
func main() {
const limit = 50_000_000
count := 0
var ud50s []int
pow := 50
for n := range genUpsideDown(limit) {
count++
if count < 50 {
ud50s = append(ud50s, n)
} else if count == 50 {
ud50s = append(ud50s, n)
fmt.Println("First 50 upside down numbers:")
rcu.PrintTable(ud50s, 10, 5, true)
fmt.Println()
pow = 500
} else if count == pow {
fmt.Printf("%sth : %s\n", rcu.Commatize(pow), rcu.Commatize(n))
pow *= 10
}
}
}
- Output:
First 50 upside down numbers: 5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1,199 1,289 1,379 1,469 1,559 1,649 1,739 1,829 1,919 2,198 2,288 2,378 2,468 2,558 2,648 2,738 2,828 2,918 3,197 3,287 3,377 3,467 3,557 3,647 3,737 3,827 3,917 4,196 4,286 4,376 4,466 500th : 494,616 5,000th : 56,546,545 50,000th : 6,441,469,664 500,000th : 729,664,644,183 5,000,000th : 82,485,246,852,682 50,000,000th : 9,285,587,463,255,281
Haskell
import Data.Char ( digitToInt )
import Data.List ( unfoldr , (!!) )
findLimits :: (Int , Int) -> [(Int , Int)]
findLimits (st , end ) = unfoldr(\(x , y ) -> if x > y then Nothing else
Just ((x , y ) , (x + 1 , y - 1 ))) (st , end )
isUpsideDown :: Int -> Bool
isUpsideDown n
|elem '0' str = False
|otherwise = all (\(a , b ) -> digitToInt( str !! a ) + digitToInt ( str !!
b ) == 10 ) $ findLimits ( 0 , length str - 1 )
where
str = show n
main :: IO ( )
main = do
let upsideDowns = take 5000 $ filter isUpsideDown [1..]
putStrLn "The first fifty upside-down numbers!"
print $ take 50 upsideDowns
putStr "The five hundredth such number : "
print $ upsideDowns !! 499
putStr "The five thousandth such number : "
print $ last upsideDowns
- Output:
The first fifty upside-down numbers! [5,19,28,37,46,55,64,73,82,91,159,258,357,456,555,654,753,852,951,1199,1289,1379,1469,1559,1649,1739,1829,1919,2198,2288,2378,2468,2558,2648,2738,2828,2918,3197,3287,3377,3467,3557,3647,3737,3827,3917,4196,4286,4376,4466] The five hundredth such number : 494616 The five thousandth such number : 56546545
Java
import java.util.List;
public final class UpsideDownNumbers {
public static void main(String[] args) {
System.out.println("The first 50 upside-down numbers:");
for ( int i = 1; i <= 50; i++ ) {
System.out.print(String.format("%4s%s", indexedUDNumber(i), ( i % 10 == 0 ) ? "\n" : " " ));
}
System.out.println();
List<Long> indexes = List.of(
50_000L, 500_000L, 5_000_000L, 5_000_000_000L, 5_000_000_000_000L, 5_000_000_000_000_000L );
indexes.forEach( index ->
System.out.println("The " + index + "th upside-down number is " + indexedUDNumber(index)));
}
private static String indexedUDNumber(long index) {
int digitCount = 1;
long first = 1, last = 1, lastIndex = 1;
while ( index > last ) {
first = last + 1;
digitCount += 1;
if ( digitCount % 2 == 0 ) {
lastIndex *= 9;
}
last = first + lastIndex - 1;
}
return nextDigits(index - first + 1, digitCount, lastIndex);
}
private static String nextDigits(long firstIndex, int digitCount, long lastIndex) {
if ( digitCount <= 1 ) {
return "5".repeat(digitCount);
}
lastIndex /= 9;
final long d = ( firstIndex - 1 ) / lastIndex;
firstIndex -= d * lastIndex;
return String.valueOf(1 + d) + nextDigits(firstIndex, digitCount - 2, lastIndex)
+ String.valueOf(9 - d);
}
}
- Output:
The first 50 upside-down numbers: 5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 The 50000th upside-down number is 6441469664 The 500000th upside-down number is 729664644183 The 5000000th upside-down number is 82485246852682 The 5000000000th upside-down number is 269222738456273888148 The 5000000000000th upside-down number is 751766588225456588225443953 The 5000000000000000th upside-down number is 1513835774459212468981566335727959
jq
Adapted from Wren
Works with gojq, the Go implementation of jq, and with fq
The following solution relies on the built-in integer arithmetic capabilities of the selected implementation of jq. In the case of the C implementation, this precludes in principle the completion of the stretch task. In any case, the program below becomes very slow after the 50,000th upside-down number is generated, whichever of the above-mentioned implementations of jq is used.
# Output an unbounded stream of upside-down numbers
def genUpsideDown:
def wrappings: [
[1, 9], [2, 8], [3, 7], [4, 6], [5, 5],
[6, 4], [7, 3], [8, 2], [9, 1] ];
{ evens: [19, 28, 37, 46, 55, 64, 73, 82, 91],
odds: [5],
oddIndex: 0, evenIndex: 0, ndigits: 1, pow: 100 }
| while (true;
.emit = null
| if .ndigits % 2 == 1
then if (.odds|length) > .oddIndex
then .emit = .odds[.oddIndex]
| .oddIndex += 1
else # build next odds, but switch to evens
.nextOdds = []
| reduce wrappings[] as $w (.;
reduce .odds[] as $i (.;
.nextOdds += [$w[0] * .pow + $i * 10 + $w[1]] ) )
| .odds = .nextOdds
| .ndigits += 1
| .pow *= 10
| .oddIndex = 0
end
elif (.evens|length) > .evenIndex
then .emit = .evens[.evenIndex]
| .evenIndex += 1
else # build next evens, but switch to odds
.nextEvens = []
| reduce wrappings[] as $w (.;
reduce .evens[] as $i (.;
.nextEvens += [$w[0] * .pow + $i * 10 + $w[1]] ) )
| .evens = .nextEvens
| .ndigits += 1
| .pow *= 10
| .evenIndex = 0
end )
| select(.emit).emit ;
def task($limit):
{ count:0, ud50s: [], pow: 50 }
| foreach limit($limit; genUpsideDown) as $n (.;
.emit = null
| .count += 1
| if .count < 50
then .ud50s += [$n]
elif .count == 50
then .emit = {"First 50 upside down numbers:": (.ud50s + [$n]) }
| .pow = 500
elif .count == .pow
then .emit = {pow, $n}
| .pow *= 10
else .
end)
| select(.emit).emit;
task(5000000)
- Output:
The jq and gojq programs were terminated after the results shown below were obtained.
{"First 50 upside down numbers:":[5,19,28,37,46,55,64,73,82,91,159,258,357,456,555,654,753,852,951,1199,1289,1379,1469,1559,1649,1739,1829,1919,2198,2288,2378,2468,2558,2648,2738,2828,2918,3197,3287,3377,3467,3557,3647,3737,3827,3917,4196,4286,4376,4466]} {"pow":500,"n":494616} {"pow":5000,"n":56546545} {"pow":50000,"n":6441469664}
Julia
using Formatting
using ResumableFunctions
@resumable function gen_upsidedowns()
""" generate upside-down numbers (OEIS A299539) """
wrappings = [[1, 9], [2, 8], [3, 7], [4, 6],
[5, 5], [6, 4], [7, 3], [8, 2], [9, 1]]
evens = [19, 28, 37, 46, 55, 64, 73, 82, 91]
odds = [5]
ndigits, odd_index, even_index, olen, elen = 1, 0, 0, 1, 9
while true
if isodd(ndigits)
if olen > odd_index
@yield odds[begin + odd_index]
odd_index += 1
else
# build next odds, but switch to evens
odds = [hi * 10^(ndigits + 1) + 10 * i + lo for i in odds, (hi, lo) in wrappings]
ndigits += 1
odd_index = 0
olen = length(odds)
end
else
if elen > even_index
@yield evens[begin + even_index]
even_index += 1
else
# build next evens, but switch to odds
evens = [hi * 10^(ndigits + 1) + 10 * i + lo for i in evens, (hi, lo) in wrappings]
ndigits += 1
even_index = 0
elen = length(evens)
end
end
end
end
println("First fifty upside-downs:")
for (udcount, udnumber) in enumerate(gen_upsidedowns())
if udcount <= 50
print(lpad(udnumber, 5), udcount % 10 == 0 ? "\n" : "")
elseif udcount == 500
println("\nFive hundredth: ", format(udnumber, commas = true))
elseif udcount == 5000
println("Five thousandth: ", format(udnumber, commas = true))
elseif udcount == 50_000
println("Fifty thousandth: ", format(udnumber, commas = true))
elseif udcount == 500_000
println("Five hundred thousandth: ", format(udnumber, commas = true))
elseif udcount == 5_000_000
println("Five millionth: ", format(udnumber, commas = true))
break
end
end
- Output:
First fifty upside-downs: 5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 Five hundredth: 494,616 Five thousandth: 56,546,545 Fifty thousandth: 6,441,469,664 Five hundred thousandth: 729,664,644,183 Five millionth: 82,485,246,852,682
Nim
import std/[math, strformat, strutils, sugar]
iterator upsideDownNumbers(): (int, int) =
## Generate upside-down numbers (OEIS A299539).
const
Wrappings = [(1, 9), (2, 8), (3, 7), (4, 6),
(5, 5), (6, 4), (7, 3), (8, 2), (9, 1)]
var
evens = @[19, 28, 37, 46, 55, 64, 73, 82, 91]
odds = @[5]
oddIndex, evenIndex = 0
ndigits = 1
count = 0
while true:
if ndigits mod 2 == 1:
if odds.len > oddIndex:
inc count
yield (count, odds[oddIndex])
inc oddIndex
else:
# Build next odds, but switch to evens.
odds = collect:
for (hi, lo) in Wrappings:
for i in odds:
hi * 10^(ndigits + 1) + 10 * i + lo
inc ndigits
oddIndex = 0
else:
if evens.len > evenIndex:
inc count
yield (count, evens[evenIndex])
inc evenIndex
else:
# Build next evens, but switch to odds.
evens = collect:
for (hi, lo) in Wrappings:
for i in evens:
hi * 10^(ndigits + 1) + 10 * i + lo
inc ndigits
evenIndex = 0
echo "First fifty upside-downs:"
for (udcount, udnumber) in upsideDownNumbers():
if udcount <= 50:
stdout.write &"{udnumber:5}"
if udcount mod 10 == 0: echo()
elif udcount == 500:
echo &"\nFive hundredth: {insertSep($udnumber)}"
elif udcount == 5_000:
echo &"Five thousandth: {insertSep($udnumber)}"
elif udcount == 50_000:
echo &"Fifty thousandth: {insertSep($udnumber)}"
elif udcount == 500_000:
echo &"Five hundred thousandth: {insertSep($udnumber):}"
elif udcount == 5_000_000:
echo &"Five millionth: {insertSep($udnumber):}"
break
- Output:
First fifty upside-downs: 5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 Five hundredth: 494_616 Five thousandth: 56_546_545 Fifty thousandth: 6_441_469_664 Five hundred thousandth: 729_664_644_183 Five millionth: 82_485_246_852_682
Pascal
Free Pascal
extended to 50E6. Added direct calculation of n-th Upside-Down number.
up to High(Uint64)-1 = 18446744073709551614.th
program UpSideDownNumbers;
{$IFDEF FPC}{$MODE DELPHI}{$Optimization ON,All}{$ENDIF}
{$IFDEF Windows}{$APPTYPE CONSOLE}{$ENDIF}
//count of UpSideDownNumbers until dgt
//1,+1,+9,+9,+9*9,+9*9,+9*9*9,...
const TotalCnt_Dgt : array[0..41] of Uint64=
(1,2,11,20,101,182,911,1640,8201,14762,73811,132860,664301,1195742,
5978711,10761680,53808401,96855122,484275611,871696100,4358480501,
7845264902,39226324511,70607384120,353036920601,635466457082,
3177332285411,5719198113740,28595990568701,51472783023662,
257363915118311,463255047212960,2316275236064801,4169295424916642,
20846477124583211,37523658824249780,187618294121248901,
337712929418248022,1688564647091240111,3039416364764232200,
15197081823821161001,HIGH(UINT64));
type
tUpDown = record
UD_half : array[0..21] of Int32;
UD_Dgt : Int32;
end;
function EmitUpDownNumber(const UD :tUpDown):Ansistring;
var
i,dc,idx : Int32;
begin
with UD do
Begin
dc := UD_Dgt;
setlength(result,dc);
dc := dc shr 1 -1;
idx := 1;
For i := dc downto 0 do
Begin
result[idx] := chr(UD_half[i]+Ord('0'));
inc(idx);
end;
if Odd(UD_Dgt) then
Begin
result[idx] := '5';
inc(idx);
end;
For i := 0 to dc do
Begin
result[idx] := chr(10+Ord('0')-UD_half[i]);
inc(idx);
end;
end;
end;
procedure NthUpDownNumber(n : Uint64;var UD:tUpDown);
var
dgtCnt,i : Int32;
begin
dgtCnt := 1;
while (dgtCnt<= High(TotalCnt_Dgt)) AND (n>= TotalCnt_Dgt[dgtCnt]) do
inc(dgtCnt);
with UD do
begin
UD_Dgt := dgtCnt;
n -= TotalCnt_Dgt[dgtCnt-1];
if dgtCnt > 1 then
begin
dgtCnt := dgtCnt SHR 1-1;
i := dgtcnt;
repeat
UD_half[i-dgtcnt] := n mod 9+1;
n := n div 9;
dec(dgtCnt);
until dgtCnt <0;
end;
end;
end;
procedure NextNumb(var UD:tUpDown);
var
i,dc,dgt : Uint32;
begin
with UD do
begin
dc:= UD_Dgt;
if dc>1 then
Begin
i := 0;
dc := dc shr 1-1;
repeat
dgt := UD_half[i]+1;
if dgt <10 then
begin
UD_half[i] := dgt;
BREAK;
end;
UD_half[i] := 1;
inc(i);
until i > dc;
if i > dc then
Begin
UD_half[i]:= 1;
inc(UD_Dgt);
end;
end
else
begin
inc(UD_Dgt);
UD_half[0] := 1;
end;
end;
end;
var
{$ALIGN 32}
UD1,Ud2 : tUpDown;
Count,
limit : UInt64;
Begin
Count := 0;
limit := 50;
Writeln('First fifty upside-downs:');
limit := 50;
repeat
NextNumb(UD1);
inc(Count);
write(EmitUpDownNumber(UD1):5);
if Count MOD 10 = 0 then
writeln;
until Count>=limit;
writeln;
writeln(' digits count value');
repeat
repeat
NextNumb(UD1);inc(Count);
until count >= limit;
NthUpDownNumber(count,UD2);
writeln(' next ',UD1.UD_Dgt:3,count:10,EmitUpDownNumber(UD1):20);
writeln(' calc ',UD2.UD_Dgt:3,count:10,EmitUpDownNumber(UD2):20);
limit *= 10;
until Limit > 50*1000*1000 ;
writeln;
limit :=TotalCnt_Dgt[High(TotalCnt_Dgt)-1]-1;
NthUpDownNumber(Limit,UD2);
writeln(limit:20,UD2.UD_Dgt:6,EmitUpDownNumber(UD2):20*2+2);
inc(limit);
writeln('+1':20);
NthUpDownNumber(Limit,UD2);
writeln(limit:20,UD2.UD_Dgt:6,EmitUpDownNumber(UD2):20*2+2,#13);
writeln('Highest nth High(Uint64)-1');
limit := TotalCnt_Dgt[High(TotalCnt_Dgt)]-1;
NthUpDownNumber(Limit,UD2);
writeln(limit:20,UD2.UD_Dgt:6,EmitUpDownNumber(UD2):20*2+2,#13);
end.
- @TIO.RUN:
First fifty upside-downs: 5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 digits count value next 4 51 4556 calc 4 51 4556 next 6 500 494616 calc 6 500 494616 next 8 5000 56546545 calc 8 5000 56546545 next 10 50000 6441469664 calc 10 50000 6441469664 next 12 500000 729664644183 calc 12 500000 729664644183 next 14 5000000 82485246852682 calc 14 5000000 82485246852682 next 16 50000000 9285587463255281 calc 16 50000000 9285587463255281 15197081823821161000 40 9999999999999999999911111111111111111111 +1 15197081823821161001 41 11111111111111111111599999999999999999999 Highest nth High(Uint64)-1 18446744073709551614 41 34687465242995612644566489451186854632467 Real time: 0.271 s CPU share: 99.00 %
Perl
use v5.36;
use Lingua::EN::Numbers qw(num2en_ordinal);
sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
sub table ($c, @V) { my $t = $c * (my $w = 5); ( sprintf( ('%'.$w.'d')x@V, @V) ) =~ s/.{1,$t}\K/\n/gr }
sub updown ($n) {
my($i,@ud);
while (++$i) {
next if subset($i, '0', 0) or 0 != ($i+reverse $i) % 10;
my @i = split '', $i;
next if grep { 10 != $i[$_] + $i[$#i-$_] } 0..$#i;
push @ud, $i;
last if $n == @ud;
}
@ud
}
my @ud = updown( 5000 );
say "First fifty upside-downs:\n" . table 10, @ud[0..49];
say ucfirst num2en_ordinal($_) . ': ' . comma $ud[$_-1] for 500, 5000;
- Output:
First fifty upside-downs: 5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 Five hundredth: 494,616 Five thousandth: 56,546,545
Phix
Finishes instantly
with javascript_semantics
atom t0 = time()
function get_counts(integer d)
atom count = 1,
first = 1,
last = 1
for i=2 to d do
first = last+1
if even(i) then count *=9 end if
last = first+count-1
end for
return {count,d,first,ord(first),last,ord(last)}
end function
function kth_of_n(atom kth, digits, count)
if digits=0 then return "" end if
if digits=1 then
assert(kth=1 and count=1) -- (might as well check)
return "5"
end if
count /= 9 -- (count should always be 9,81,729,... here)
integer d = floor((kth-1)/count)
kth -= d*count
return ('1'+d) & kth_of_n(kth,digits-2,count) & ('9'-d)
end function
function get_which(atom nth)
integer digits = 1
atom count = 1,
first = 1,
last = 1
while nth>last do
first = last+1
digits += 1
if even(digits) then count *=9 end if
last = first+count-1
end while
atom kth = nth-first+1
string res = kth_of_n(kth,digits,count)
return {nth, ord(nth), kth, ord(kth), digits, res}
end function
string fmt = "The first 50 upside down numbers:\n%s\n"
printf(1,fmt,join_by(vslice(apply(tagset(50),get_which),6),1,10,fmt:="%4s"))
-- Let's just spell it out for you...
fmt = "There are %,d %d-digit upside down numbers (the %,d%s to %,d%s)\n"
for d=1 to 7 do
printf(1,fmt,get_counts(d))
end for
printf(1,"(etc...)\n\n")
fmt = "The %,d%s upside down number is the %,d%s %d-digit number (%s)\n"
for w in {1,2,10,11,182,500,910,911,5000,50000,500000,5000000,50000000,
500000000,5000000000,50000000000,500000000000,5000000000000,
50000000000000,500000000000000,5000000000000000} do
printf(1,fmt,get_which(w))
end for
fmt = "The total time taken for this onerous and difficult task: %s\n"
printf(1,fmt,elapsed(time()-t0))
- Output:
The first 50 upside down numbers: 5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 There are 1 1-digit upside down numbers (the 1st to 1st) There are 9 2-digit upside down numbers (the 2nd to 10th) There are 9 3-digit upside down numbers (the 11th to 19th) There are 81 4-digit upside down numbers (the 20th to 100th) There are 81 5-digit upside down numbers (the 101st to 181st) There are 729 6-digit upside down numbers (the 182nd to 910th) There are 729 7-digit upside down numbers (the 911th to 1,639th) (etc...) The 1st upside down number is the 1st 1-digit number (5) The 2nd upside down number is the 1st 2-digit number (19) The 10th upside down number is the 9th 2-digit number (91) The 11th upside down number is the 1st 3-digit number (159) The 182nd upside down number is the 1st 6-digit number (111999) The 500th upside down number is the 319th 6-digit number (494616) The 910th upside down number is the 729th 6-digit number (999111) The 911th upside down number is the 1st 7-digit number (1115999) The 5,000th upside down number is the 3,361st 8-digit number (56546545) The 50,000th upside down number is the 35,239th 10-digit number (6441469664) The 500,000th upside down number is the 367,141st 12-digit number (729664644183) The 5,000,000th upside down number is the 3,804,259th 14-digit number (82485246852682) The 50,000,000th upside down number is the 39,238,321st 16-digit number (9285587463255281) The 500,000,000th upside down number is the 15,724,390th 19-digit number (1436368345672474769) The 5,000,000,000th upside down number is the 641,519,500th 21-digit number (269222738456273888148) The 50,000,000,000th upside down number is the 10,773,675,490th 23-digit number (41835623444566678457296) The 500,000,000,000th upside down number is the 146,963,079,400th 25-digit number (5724139689945611241796835) The 5,000,000,000,000th upside down number is the 1,822,667,714,590th 27-digit number (751766588225456588225443953) The 50,000,000,000,000th upside down number is the 21,404,009,431,300th 29-digit number (94816546925914569158146549261) The 500,000,000,000,000th upside down number is the 36,744,952,787,041st 32-digit number (12651942383972646483172786195489) The 5,000,000,000,000,000th upside down number is the 830,704,575,083,359th 34-digit number (1513835774459212468981566335727959) The total time taken for this onerous and difficult task: 0s
higher limits
Limited to the 18,446,744,073,709,551,614th?, we can do better than that! (and still finish instantly)
with javascript_semantics
atom t0 = time()
include mpfr.e -- (so that nth etc can exceed 64 bits of precision)
function kth_of_n(mpz kth, count, integer digits)
if digits=0 then return "" end if
if digits=1 then return "5" end if
mpz_divexact_ui(count,count,9)
mpz_sub_si(kth,kth,1)
mpz dz = mpz_init()
mpz_fdiv_q(dz,kth,count)
integer d = mpz_get_integer(dz)
mpz_add_ui(kth,kth,1)
mpz_mul(dz,dz,count)
mpz_sub(kth,kth,dz)
return ('1'+d) & kth_of_n(kth,count,digits-2) & ('9'-d)
end function
function get_which(mpz nth)
integer digits = 1
mpz count = mpz_init(1),
first = mpz_init(1),
last = mpz_init(1)
while mpz_cmp(nth,last)>0 do
mpz_add_si(first,last,1)
digits += 1
if even(digits) then mpz_mul_si(count,count,9) end if
mpz_add(last,first,count)
mpz_sub_ui(last,last,1)
end while
mpz kth = mpz_init(1)
mpz_add(kth,kth,nth)
mpz_sub(kth,kth,first)
string ns = mpz_get_str(nth,10,true),
res = kth_of_n(kth,count,digits)
return {ns, res, elapsed(time()-t0)}
end function
printf(1,"The %sth upside down number is\n %s (%s)\n",get_which(mpz_init("1e100")))
- Output:
The 10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000th upside down number is 454594394343883179243759282183821923122343988685136868482218367266879951778395152999458916423484426556989121455486626786491256111859517233951132448347298826242479524221767889781982729828153768139722767617615656 (0.0s)
Python
""" rosettacode.org task Upside-down_numbers """
def gen_upside_down_number():
""" generate upside-down numbers (OEIS A299539) """
wrappings = [[1, 9], [2, 8], [3, 7], [4, 6],
[5, 5], [6, 4], [7, 3], [8, 2], [9, 1]]
evens = [19, 28, 37, 46, 55, 64, 73, 82, 91]
odds = [5]
odd_index, even_index = 0, 0
ndigits = 1
while True:
if ndigits % 2 == 1:
if len(odds) > odd_index:
yield odds[odd_index]
odd_index += 1
else:
# build next odds, but switch to evens
odds = [hi * 10**(ndigits + 1) + 10 *
i + lo for hi, lo in wrappings for i in odds]
ndigits += 1
odd_index = 0
else:
if len(evens) > even_index:
yield evens[even_index]
even_index += 1
else:
# build next evens, but switch to odds
evens = [hi * 10**(ndigits + 1) + 10 *
i + lo for hi, lo in wrappings for i in evens]
ndigits += 1
even_index = 0 even_index = 0
print('First fifty upside-downs:')
for (udcount, udnumber) in enumerate(gen_upside_down_number()):
if udcount < 50:
print(f'{udnumber : 5}', end='\n' if (udcount + 1) % 10 == 0 else '')
elif udcount == 499:
print(f'\nFive hundredth: {udnumber: ,}')
elif udcount == 4999:
print(f'\nFive thousandth: {udnumber: ,}')
elif udcount == 49_999:
print(f'\nFifty thousandth: {udnumber: ,}')
elif udcount == 499_999:
print(f'\nFive hundred thousandth: {udnumber: ,}')
elif udcount == 4_999_999:
print(f'\nFive millionth: {udnumber: ,}')
break
- Output:
First fifty upside-downs: 5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 Five hundredth: 494,616 Five thousandth: 56,546,545 Fifty thousandth: 6,441,469,664 Five hundred thousandth: 729,664,644,183 Five millionth: 82,485,246,852,682
Quackery
(Load extensions for the faster merge sort.)
Method
Start with generation zero as the empty string and "5". Make the next generation by expanding the previous generation (expand
) i.e. wrapping each of the strings in "1" and "9", "2" and "8" … "8" and "2", "9" and "1". Accumulate the generations. The accumulator starts with "5", after one iteration it has "5", "19", "28" … "82", "91", "159", "258" … "852", "951".
Note that this does not produce the numbers in numerical order. It's close to numerical order but not quite there. So once sufficient numbers have been produced to guarantee that all the numbers in the required range have been calculated, convert them from string format to numerical format and sort, then truncate the list of upside down numbers to the required length.
necessary
computes a safe number of items to include in the list to guarantee that none are missing from the truncated list - i.e. the length of the list after each iteration of expand
. It is (9^n - 5) / 4
, where n
is the number of iterations. (OEIS A211866)
^
in necessary
is bitwise XOR, not exponentiation.
[ 0
[ 2dup > while
1 ^ 9 * 1+ again ]
nip ] is necessary ( n --> n )
[ [] swap
witheach
[ ' [ [ char 1 char 9 ]
[ char 2 char 8 ]
[ char 3 char 7 ]
[ char 4 char 6 ]
[ char 5 char 5 ]
[ char 6 char 4 ]
[ char 7 char 3 ]
[ char 8 char 2 ]
[ char 9 char 1 ] ]
witheach
[ over dip do
dip swap join
swap join nested
rot swap join
swap ]
drop ] ] is expand ( [ --> [ )
[ dup necessary temp put
' [ [ char 5 ] ]
' [ [ ] [ char 5 ] ]
[ expand tuck join swap
over size
temp share < not
until ]
drop
temp release
[] swap
witheach
[ $->n drop join ]
sort
swap split drop ] is upsidedowns ( n --> [ )
5000 upsidedowns
say "First 50 upside down numbers:"
dup 50 split drop
[] swap witheach
[ number$ nested join ]
45 wrap$
cr cr
say "500th upside down number: "
dup 499 peek echo
cr
say "5000th upside down number: "
4999 peek echo
- Output:
First 50 upside down numbers: 5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 500th upside down number: 494616 5000th upside down number: 56546545
Raku
use Lingua::EN::Numbers;
sub udgen (@r) {
my @u = @r.hyper.map: { next if .contains: 0; ($_, (10 «-« .flip.comb).join) };
@u».join, @u».join(5)
}
my @upside-downs = lazy flat 5, (^∞).map({ udgen exp($_,10) .. exp(1+$_,10) });
say "First fifty upside-downs:\n" ~ @upside-downs[^50].batch(10)».fmt("%4d").join: "\n";
say '';
for 5e2, 5e3, 5e4, 5e5, 5e6 {
say "{.Int.&ordinal.tc}: " ~ comma @upside-downs[$_-1]
}
- Output:
First fifty upside-downs: 5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 Five hundredth: 494,616 Five thousandth: 56,546,545 Fifty thousandth: 6,441,469,664 Five hundred thousandth: 729,664,644,183 Five millionth: 82,485,246,852,682
RPL
RPL code | Comment |
---|---|
≪ 9 SWAP 2 / CEIL ^ ≫ 'POW92' STO ≪ SWAP 1 - "" SWAP 1 4 ROLL START 9 MOD LAST / FLOOR SWAP 1 + →STR ROT + SWAP NEXT DROP ≫ '→STR9' STO ≪ → str ≪ "" str SIZE 1 FOR j 106 str j DUP SUB NUM - CHR + -1 STEP ≫ ≫ 'UDSTR' STO ≪ IF DUP 1 == THEN DROP "5" ELSE 1 WHILE OVER 1 > REPEAT SWAP OVER POW92 - SWAP 1 + END 1 - DUP POW92 ROT + 1 - → series order ≪ order series 2 / CEIL →STR9 DUP IF order 2 MOD NOT THEN "5" + END SWAP UDSTR + ≫ END ≫ 'UPSDN' STO |
POW92 ( n -- 9^ceil(n/2) ) →STR9 ( n str_length -- "12..9" ) n-- ; s = "" ; loop size times n,m = divmod(n) append "m+1" to s return s UDSTR ( "str" -- "rts" ) s = "" ; loop for j from size(str) downto 1 s[j] = 106 - char(ascii(str[j])) return s UPSDN ( n -- "a(n)" ) if n = 1 then return "5" else series = 1 ; while n > 1 n -= 9^ceil(series/2); series++ series-- ; order = n + 9^ceil(series/2) + 1 Create left part of the upside-down number, as a string Add 5 in the middle if appropriate Add upside-down right part et voilà return full string |
- Input:
≪ {} 1 50 FOR j j UPSDN+ NEXT ≫ EVAL 500 UPSDN 5000 UPSDN 50000 UPSDN 500000 UPSDN 5000000 UPSDN 5000000000 UPSDN
- Output:
7: { "5" "19" "28" "37" "46" "55" "64" "73" "82" "91" "159" "258" "357" "456" "555" "654" "753" "852" "951" "1199" "1289" "1379" "1469" "1559" "1649" "1739" "1829" "1919" "2198" "2288" "2378" "2468" "2558" "2648" "2738" "2828" "2918" "3197" "3287" "3377" "3467" "3557" "3647" "3737" "3827" "3917" "4196" "4286" "4376" "4466" } 6: "494616" 5: "56546545" 4: "6441469664" 3: "729664644183" 2: "82485246852682" 1: "269222738456273888148"
Ruby
DIGITS =(1..9).to_a
updowns = Enumerator.new do |y|
y << 5
(1..).each do |s|
perms = DIGITS.repeated_permutation(s)
perms.each{|perm| y << (perm + perm.reverse.map{|n| 10-n}).join.to_i }
perms.each{|perm| y << (perm + [5] + perm.reverse.map{|n| 10-n}).join.to_i }
end
end
res = updowns.take(5000000)
res.first(50).each_slice(10){|slice| puts "%6d"*slice.size % slice}
puts
n = 500
5.times do
puts "%8d: %-10d" % [n, res[n-1]]
n *= 10
end
- Output:
5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 500th : 494616 5000th : 56546545 50000th : 6441469664 500000th : 729664644183 5000000th : 82485246852682
Rust
fn is_upside_down( num : u32 ) -> bool {
let numberstring : String = num.to_string( ) ;
let len = numberstring.len( ) ;
let numberstr = numberstring.as_str( ) ;
if numberstr.contains( "0" ) {
return false ;
}
if len % 2 == 1 && numberstr.chars( ).nth( len / 2 ).unwrap( ) != '5' {
return false ;
}
let mut forward : usize = 0 ;
let mut backward : usize = len - 1 ;
while forward <= backward {
let first = numberstr.chars( ).nth( forward ).expect("No digit!").
to_digit( 10 ).unwrap( ) ;
let second = numberstr.chars( ).nth( backward ).expect("No digit!").
to_digit( 10 ).unwrap( ) ;
if first + second != 10 {
return false ;
}
forward += 1 ;
if backward != 0 {
backward -= 1 ;
}
}
true
}
fn main() {
let mut solution : Vec<u32> = Vec::new( ) ;
let mut sum : u32 = 0 ;
let mut current : u32 = 0 ;
while sum < 50 {
current += 1 ;
if is_upside_down( current ) {
solution.push( current ) ;
sum += 1 ;
}
}
let five_hundr : u32 ;
while sum != 500 {
current += 1 ;
if is_upside_down( current ) {
sum += 1 ;
}
}
five_hundr = current ;
let five_thous : u32 ;
while sum != 5000 {
current += 1 ;
if is_upside_down( current ) {
sum += 1 ;
}
}
five_thous = current ;
println!("The first 50 upside-down numbers:") ;
println!("{:?}" , solution ) ;
println!("The five hundredth such number : {}" , five_hundr) ;
println!("The five thousandth such number : {}" , five_thous ) ;
}
- Output:
The first 50 upside-down numbers: [5, 19, 28, 37, 46, 55, 64, 73, 82, 91, 159, 258, 357, 456, 555, 654, 753, 852, 951, 1199, 1289, 1379, 1469, 1559, 1649, 1739, 1829, 1919, 2198, 2288, 2378, 2468, 2558, 2648, 2738, 2828, 2918, 3197, 3287, 3377, 3467, 3557, 3647, 3737, 3827, 3917, 4196, 4286, 4376, 4466] The five hundredth such number : 494616 The five thousandth such number : 56546545
Wren
import "./fmt" for Fmt
var genUpsideDown = Fiber.new {
var wrappings = [
[1, 9], [2, 8], [3, 7], [4, 6], [5, 5],
[6, 4], [7, 3], [8, 2], [9, 1]
]
var evens = [19, 28, 37, 46, 55, 64, 73, 82, 91]
var odds = [5]
var oddIndex = 0
var evenIndex = 0
var ndigits = 1
var pow = 100
while (true) {
if (ndigits % 2 == 1) {
if (odds.count > oddIndex) {
Fiber.yield(odds[oddIndex])
oddIndex = oddIndex + 1
} else {
// build next odds, but switch to evens
var nextOdds = []
for (w in wrappings) {
for (i in odds) {
nextOdds.add(w[0] * pow + i * 10 + w[1])
}
}
odds = nextOdds
ndigits = ndigits + 1
pow = pow * 10
oddIndex = 0
}
} else {
if (evens.count > evenIndex) {
Fiber.yield(evens[evenIndex])
evenIndex = evenIndex + 1
} else {
// build next evens, but switch to odds
var nextEvens = []
for (w in wrappings) {
for (i in evens) {
nextEvens.add(w[0] * pow + i * 10 + w[1])
}
}
evens = nextEvens
ndigits = ndigits + 1
pow = pow * 10
evenIndex = 0
}
}
}
}
var limit = 5000000
var count = 0
var ud50s = []
var pow = 50
while (count < limit) {
var n = genUpsideDown.call()
count = count + 1
if (count < 50) {
ud50s.add(n)
} else if (count == 50) {
System.print("First 50 upside down numbers:")
Fmt.tprint("$,5d", ud50s + [n], 10)
System.print()
pow = 500
} else if (count == pow) {
Fmt.print("$,r : $,d", pow, n)
pow = pow * 10
}
}
- Output:
First 50 upside down numbers: 5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1,199 1,289 1,379 1,469 1,559 1,649 1,739 1,829 1,919 2,198 2,288 2,378 2,468 2,558 2,648 2,738 2,828 2,918 3,197 3,287 3,377 3,467 3,557 3,647 3,737 3,827 3,917 4,196 4,286 4,376 4,466 500th : 494,616 5,000th : 56,546,545 50,000th : 6,441,469,664 500,000th : 729,664,644,183 5,000,000th : 82,485,246,852,682
XPL0
func HasZero(N); \Return 'true' if N contains a zero digit
int N;
[repeat N:= N/10;
if rem(0) = 0 then return true;
until N = 0;
return false;
];
proc IntRevOut(N); \Show N upside down
int N;
[repeat N:= N/10;
IntOut(0, 10-rem(0));
until N = 0;
];
int Count, TenPower, Limit, Out5, LeftSide;
[Count:= 1; TenPower:= 1; Limit:= 500;
IntOut(0, 5); ChOut(0, 9\tab\);
loop [Out5:= false;
repeat LeftSide:= TenPower;
repeat if not HasZero(LeftSide) then
[Count:= Count+1;
if Count <= 50 then
[IntOut(0, LeftSide);
if Out5 then IntOut(0, 5);
IntRevOut(LeftSide);
ChOut(0, 9\tab\);
if rem(Count/10) = 0 then CrLf(0);
];
if Count = Limit then
[IntOut(0, Count); Text(0, "th: ");
IntOut(0, LeftSide);
if Out5 then IntOut(0, 5);
IntRevOut(LeftSide);
CrLf(0);
Limit:= Limit*10;
if Limit > 5_000_000 then quit;
];
];
LeftSide:= LeftSide+1;
until LeftSide = TenPower*10;
Out5:= not Out5;
until not Out5;
TenPower:= TenPower*10;
];
]
- Output:
5 19 28 37 46 55 64 73 82 91 159 258 357 456 555 654 753 852 951 1199 1289 1379 1469 1559 1649 1739 1829 1919 2198 2288 2378 2468 2558 2648 2738 2828 2918 3197 3287 3377 3467 3557 3647 3737 3827 3917 4196 4286 4376 4466 500th: 494616 5000th: 56546545 50000th: 6441469664 500000th: 729664644183 5000000th: 82485246852682