Numbers with same digit set in base 10 and base 16: Difference between revisions
Line 117:
for j in 1:length(d), c in Iterators.filter(x -> length(unique(x)) == dlen,
Combinatorics.with_replacement_combinations(d, j)), p in permutations(c)
if evalpoly(16, p) == i && (length(p) == 1 || p[end] != 0 || count(x -> x == 0, p) > 1)
print(rpad(i, 6), " == 0x", rpad(evalpoly(10, p), 8), (found += 1) % 5 == 0 ? "\n" : "")
break
Line 128:
</lang>{{out}}
<pre>
33843 == 0x8433 33844 == 0x8434 33845 == 0x8435 33846 == 0x8436 33847 == 0x8437
75124 == 0x12574 75125 == 0x12575 75126 == 0x12576 75127 == 0x12577 75128 == 0x12578
91769 == 0x16679 96617 == 0x17969 98711 == 0x18197 99481 == 0x18499
</pre>
|
Revision as of 01:40, 7 June 2021
- Task
Find decimal numbers n that when converted to hexadecimal produce a number that uses the same set of digits (regardless of order and ignoring duplicates) as the original number, where n < 100000
- Example
The decimal number 2339 is 923 when written in hexadecimal.
The set of digits used, ignoring order and duplicates, is {2, 3, 9} in both cases and hence this number satisfies the task requirements.
ALGOL W
Generates the candidate numbers (ones that only have the digits 0-9 in their hexadecimal representation) to cut down the numbers to check. <lang algolw>begin % find numbers that use the same digits in decimal and hexadecimal %
integer hdCount, h20, h300, h4000, h50000; logical array hex, dec ( 0 :: 9 ); integer x2, x3, x4, x5, hx2, hx3, hx4, hx5; hdCount := 0; % note 100 000 is 186A0 in hexadecimal, so we need to consider numbers % % with up to 5 hexadedcimal digits % % powers of 16 % x2 := 16; x3 := x2 * 16; x4 := x3 * 16; x5 := x4 * 16; for hPos := 0 until 9 do hex( hPos ) := false; % construct the numbers that have only 0-9 in their hex representations % for h5 := 0 until 1 do begin hx5 := h5 * x5; for h4 := 0 until 9 do begin hx4 := h4 * x4; for h3 := 0 until 9 do begin hx3 := h3 * x3; for h2 := 0 until 9 do begin hx2 := h2 * x2; for h1 := 0 until 9 do begin integer n, d; n := d := hx5 + hx4 + hx3 + hx2 + h1; if n > 100000 then goto endSearch; for dPos := 0 until 9 do dec( dPos ) := false; if d = 0 then dec( 0 ) := true; while d > 0 do begin dec( d rem 10 ) := true; d := d div 10 end while_d_gt_0 ; if h5 not = 0 then hex( h5 ) := true; if h5 + h4 not = 0 then hex( h4 ) := true; if h5 + h4 + h3 not = 0 then hex( h3 ) := true; if h5 + h4 + h3 + h2 not = 0 then hex( h2 ) := true; hex( h1 ) := true; if hex( 0 ) = dec( 0 ) and hex( 1 ) = dec( 1 ) and hex( 2 ) = dec( 2 ) and hex( 3 ) = dec( 3 ) and hex( 4 ) = dec( 4 ) and hex( 5 ) = dec( 5 ) and hex( 6 ) = dec( 6 ) and hex( 7 ) = dec( 7 ) and hex( 8 ) = dec( 8 ) and hex( 9 ) = dec( 9 ) then begin % the decimal and hexadecimal representations % % use the same digits % writeon( i_w := 7, s_w := 0, " ", n ); hdCount := hdCount + 1; if hdCount rem 10 = 0 then write() end if_allSame ; hex( h1 ) := false; hex( h2 ) := false; hex( h3 ) := false; hex( h4 ) := false; hex( h5 ) := false; end for_h5 end for_h4 end for_h3 end for_h2 end for_h1 ;
endSearch:
write( i_w := 1, s_w := 0, "Found ", hdCount, " numbers up to 100000 " ); write( " where the decimal and hexadecimal " , "representations use the same digits" );
end.</lang>
- Output:
0 1 2 3 4 5 6 7 8 9 53 371 913 1040 2080 2339 4100 5141 5412 5441 6182 8200 9241 13593 13665 13969 16406 20530 26946 30979 32803 33638 33840 33841 33842 33843 33844 33845 33846 33847 33848 33849 34883 37943 38931 38966 38995 66310 71444 71497 71511 75120 75121 75122 75123 75124 75125 75126 75127 75128 75129 75621 86150 88165 91465 91769 96617 98711 99481 Found 69 numbers up to 100000 where the decimal and hexadecimal representations use the same digits
Factor
<lang factor>USING: formatting grouping io kernel math.parser present sequences sets ;
100,000 <iota> [ dup present swap >hex set= ] filter 10 group [ [ "%5d " printf ] each nl ] each</lang>
- Output:
0 1 2 3 4 5 6 7 8 9 53 371 913 1040 2080 2339 4100 5141 5412 5441 6182 8200 9241 13593 13665 13969 16406 20530 26946 30979 32803 33638 33840 33841 33842 33843 33844 33845 33846 33847 33848 33849 34883 37943 38931 38966 38995 66310 71444 71497 71511 75120 75121 75122 75123 75124 75125 75126 75127 75128 75129 75621 86150 88165 91465 91769 96617 98711 99481
Julia
The requirements seem to depend upon interpretations of set and duplicates. Hex number is shown to demonstrate how numbers fit the revised task. The revised task may or may not disallow leading zeros for the base 16 number. <lang Julia>using Combinatorics
function dheq(N)
found = 0 for i in 0:N d = digits(i) dlen = length(unique(d)) for j in 1:length(d), c in Iterators.filter(x -> length(unique(x)) == dlen, Combinatorics.with_replacement_combinations(d, j)), p in permutations(c) if evalpoly(16, p) == i && (length(p) == 1 || p[end] != 0 || count(x -> x == 0, p) > 1) print(rpad(i, 6), " == 0x", rpad(evalpoly(10, p), 8), (found += 1) % 5 == 0 ? "\n" : "") break end end end
end
dheq(100000)
</lang>
- Output:
0 == 0x0 1 == 0x1 2 == 0x2 3 == 0x3 4 == 0x4 5 == 0x5 6 == 0x6 7 == 0x7 8 == 0x8 9 == 0x9 53 == 0x35 371 == 0x173 913 == 0x391 1040 == 0x410 2080 == 0x820 2339 == 0x923 4100 == 0x1004 5141 == 0x1415 5412 == 0x1524 5441 == 0x1541 6182 == 0x1826 8200 == 0x2008 9241 == 0x2419 13593 == 0x3519 13665 == 0x3561 13969 == 0x3691 16406 == 0x4016 20530 == 0x5032 26946 == 0x6942 30979 == 0x7903 32803 == 0x8023 33638 == 0x8366 33840 == 0x8430 33841 == 0x8431 33842 == 0x8432 33843 == 0x8433 33844 == 0x8434 33845 == 0x8435 33846 == 0x8436 33847 == 0x8437 33848 == 0x8438 33849 == 0x8439 34883 == 0x8843 37943 == 0x9437 38931 == 0x9813 38966 == 0x9836 38995 == 0x9853 66310 == 0x10306 71444 == 0x11714 71497 == 0x11749 71511 == 0x11757 75120 == 0x12570 75121 == 0x12571 75122 == 0x12572 75123 == 0x12573 75124 == 0x12574 75125 == 0x12575 75126 == 0x12576 75127 == 0x12577 75128 == 0x12578 75129 == 0x12579 75621 == 0x12765 86150 == 0x15086 88165 == 0x15865 91465 == 0x16549 91769 == 0x16679 96617 == 0x17969 98711 == 0x18197 99481 == 0x18499
Nim
There are many ways to find the numbers. We chose to build directly the set of digits in base 10 and base 16 rather than using the string representations (more code but more efficient).
<lang Nim>import strutils, sugar
const Lim = 99_999
type Digit = 0..15
func digitSet(n: Natural; b: Positive): set[Digit] =
## Return the set of digits of "n" written in base "b". assert b <= 16 if n == 0: return {Digit 0} var n = n while n != 0: result.incl n mod b n = n div b
- Build the list of numbers.
let list = collect(newSeq):
for n in 0..Lim: if n.digitSet(10) == n.digitSet(16): n
- Display result.
echo "Found $1 numbers less than $2:".format(list.len, insertSep($(Lim + 1))) for i, n in list:
stdout.write ($n).align(5), if (i + 1) mod 10 == 0: '\n' else: ' '
echo()</lang>
- Output:
Found 69 numbers less than 100_000: 0 1 2 3 4 5 6 7 8 9 53 371 913 1040 2080 2339 4100 5141 5412 5441 6182 8200 9241 13593 13665 13969 16406 20530 26946 30979 32803 33638 33840 33841 33842 33843 33844 33845 33846 33847 33848 33849 34883 37943 38931 38966 38995 66310 71444 71497 71511 75120 75121 75122 75123 75124 75125 75126 75127 75128 75129 75621 86150 88165 91465 91769 96617 98711 99481
Phix
function handusc(integer n) return unique(sprintf("%x",n))=unique(sprintf("%d",n)) end function ?shorten(filter(tagset(100000,0),handusc),"found",10)
- Output:
{0,1,2,3,4,5,6,7,8,9,"...",75128,75129,75621,86150,88165,91465,91769,96617,98711,99481," (69 found)"}
Quackery
<lang Quackery> [ 0 swap witheach [ bit | ] ] is ->set ( [ --> s )
[ 10 base put dup number$ ->set 16 base replace swap number$ ->set base release = ] is dec=hex ( n --> b )
[] 100000 times [ i^ dec=hex if [ i^ number$ nested join ] ] 60 wrap$</lang>
- Output:
0 1 2 3 4 5 6 7 8 9 53 371 913 1040 2080 2339 4100 5141 5412 5441 6182 8200 9241 13593 13665 13969 16406 20530 26946 30979 32803 33638 33840 33841 33842 33843 33844 33845 33846 33847 33848 33849 34883 37943 38931 38966 38995 66310 71444 71497 71511 75120 75121 75122 75123 75124 75125 75126 75127 75128 75129 75621 86150 88165 91465 91769 96617 98711 99481
Raku
Much is left open to interpretation.
Numbers which when expressed in decimal and in hexadecimal are composed of the same digit glyphs. <lang perl6>say (^100000).hyper(:5000batch).grep( { [eqv] ($_, .fmt: '%x').map( *.comb.Bag ) } ).batch(10)».fmt('%5d').join("\n")</lang>
- Output:
0 1 2 3 4 5 6 7 8 9 53 371 913 4100 5141 5412 6182 8200 9241 75120 75121 75122 75123 75124 75125 75126 75127 75128 75129 75621 86150 91465 98711 99481
Numbers which when expressed in decimal and in hexadecimal are composed from the same digit glyphs. <lang perl6>say (^100000).hyper(:5000batch).grep( { [eqv] ($_, .fmt: '%x').map( *.comb.Set ) } ).batch(10)».fmt('%5d').join("\n")</lang>
- Output:
0 1 2 3 4 5 6 7 8 9 53 371 913 1040 2080 2339 4100 5141 5412 5441 6182 8200 9241 13593 13665 13969 16406 20530 26946 30979 32803 33638 33840 33841 33842 33843 33844 33845 33846 33847 33848 33849 34883 37943 38931 38966 38995 66310 71444 71497 71511 75120 75121 75122 75123 75124 75125 75126 75127 75128 75129 75621 86150 88165 91465 91769 96617 98711 99481
REXX
<lang rexx>/*REXX pgm finds integers when shown in decimal and hexadecimal use the same numerals.*/ parse arg n cols . /*obtain optional argument from the CL.*/ if n== | n=="," then n = 100000 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ w= 10 /*width of a number in any column. */
@hHex= ' decimal integers when displayed in decimal and' , "hexadecimal use the same numerals, where N < " commas(n)
say ' index │'center(@hHex, 1 + cols*(w+1) ) /*display the title for the output. */ say '───────┼'center("" , 1 + cols*(w+1), '─') /* " a sep " " " */ dHex= 0; idx= 1 /*initialize # of high hexadecimal nums*/ $= /*list of high hexadecimal #'s (so far)*/
do j=0 for n; h= d2x(j) /*search for high hexadecimal numbers. */ if verify(j, h)>0 then iterate /*Does the decimal and hexadecimal ··· */ /* ◄■■■■■■■■ a filter. */ if verify(h, j)>0 then iterate /* ··· versions use same numerals? */ /* ◄■■■■■■■■ a filter. */ dHex= dHex + 1 /*bump number of decimal-hex numbers. */ $= $ right(commas(j), w) /*add a dec-hexadecimal number──► list.*/ if dHex // cols \== 0 then iterate /*have we populated a line of output? */ say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */ idx= idx + cols /*bump the index count for the output*/ end /*j*/
if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ say '───────┴'center("" , 1 + cols*(w+1), '─') /*display the foot sep for output. */ say say 'Found ' commas(dHex) @hHex exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?</lang>
- output when using the default inputs:
index │ decimal integers when displayed in decimal and hexadecimal use the same numerals, where N < 100,000 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 0 1 2 3 4 5 6 7 8 9 11 │ 53 371 913 1,040 2,080 2,339 4,100 5,141 5,412 5,441 21 │ 6,182 8,200 9,241 13,593 13,665 13,969 16,406 20,530 26,946 30,979 31 │ 32,803 33,638 33,840 33,841 33,842 33,843 33,844 33,845 33,846 33,847 41 │ 33,848 33,849 34,883 37,943 38,931 38,966 38,995 66,310 71,444 71,497 51 │ 71,511 75,120 75,121 75,122 75,123 75,124 75,125 75,126 75,127 75,128 61 │ 75,129 75,621 86,150 88,165 91,465 91,769 96,617 98,711 99,481 ───────┴─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Found 69 decimal integers when displayed in decimal and hexadecimal use the same numerals, where N < 100,000
Ring
<lang ring> see "working..." + nl
row = 0 limit = 100000
for n = 0 to limit
flag1 = 1 flag2 = 1 decStr = string(n) hexStr = hex(n) for m = 1 to len(decStr) ind = substr(hexStr,decStr[m]) if ind < 1 flag1 = 0 exit ok next for p = 1 to len(hexStr) ind = substr(decStr,hexStr[p]) if ind < 1 flag2 = 0 exit ok next if flag1 = 1 and flag2 = 1 row = row + 1 see "" + n + " " if row%5 = 0 see nl ok ok
next
see nl + "Found " + row + " numbers" + nl see "done..." + nl </lang>
- Output:
working... 0 1 2 3 4 5 6 7 8 9 53 371 913 1040 2080 2339 4100 5141 5412 5441 6182 8200 9241 13593 13665 13969 16406 20530 26946 30979 32803 33638 33840 33841 33842 33843 33844 33845 33846 33847 33848 33849 34883 37943 38931 38966 38995 66310 71444 71497 71511 75120 75121 75122 75123 75124 75125 75126 75127 75128 75129 75621 86150 88165 91465 91769 96617 98711 99481 Found 69 numbers done...
Wren
<lang ecmascript>import "/fmt" for Conv, Fmt import "/set" for Set
var limit = 1e5 var count = 0 System.print("Numbers under 100,000 which use the same digits in decimal or hex:") for (n in 0...limit) {
var h = Conv.hex(n) var hs = Set.new(h) var ns = Set.new(n.toString) if (hs == ns) { count = count + 1 Fmt.write("$,6d ", n) if (count % 10 == 0) System.print() }
} System.print("\n\n%(count) such numbers found.")</lang>
- Output:
Numbers under 100,000 which use the same digits in decimal or hex: 0 1 2 3 4 5 6 7 8 9 53 371 913 1,040 2,080 2,339 4,100 5,141 5,412 5,441 6,182 8,200 9,241 13,593 13,665 13,969 16,406 20,530 26,946 30,979 32,803 33,638 33,840 33,841 33,842 33,843 33,844 33,845 33,846 33,847 33,848 33,849 34,883 37,943 38,931 38,966 38,995 66,310 71,444 71,497 71,511 75,120 75,121 75,122 75,123 75,124 75,125 75,126 75,127 75,128 75,129 75,621 86,150 88,165 91,465 91,769 96,617 98,711 99,481 69 such numbers found.
XPL0
<lang XPL0>func DigitSet(N, D); \Return a bit array containing the set of digits in N divisible by D int N, D; int Set; [Set:= 0; repeat N:= N/D;
Set:= Set or 1<<rem(0);
until N=0; return Set; ];
int Count, N; [Count:= 0; for N:= 0 to 99999 do
[if DigitSet(N,10) = DigitSet(N,16) then [IntOut(0, N); Count:= Count+1; if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\); ]; ];
CrLf(0); IntOut(0, Count); Text(0, " such numbers found. ") ]</lang>
- Output:
0 1 2 3 4 5 6 7 8 9 53 371 913 1040 2080 2339 4100 5141 5412 5441 6182 8200 9241 13593 13665 13969 16406 20530 26946 30979 32803 33638 33840 33841 33842 33843 33844 33845 33846 33847 33848 33849 34883 37943 38931 38966 38995 66310 71444 71497 71511 75120 75121 75122 75123 75124 75125 75126 75127 75128 75129 75621 86150 88165 91465 91769 96617 98711 99481 69 such numbers found.