Upside-down numbers
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.
Upside-down numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- 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
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
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
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 %
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 = sorted([hi * 10**(ndigits + 1) + 10 *
i + lo for i in odds for hi, lo in wrappings])
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 = sorted([hi * 10**(ndigits + 1) + 10 *
i + lo for i in evens for hi, lo in wrappings])
ndigits += 1
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
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
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