Wasteful, equidigital and frugal numbers: Difference between revisions
(Added a clarifying sentence to the task description.) |
(→{{header|J}}: omit off-by-one issue for 10000th) |
||
Line 56: | Line 56: | ||
Task examples (base 10):<lang J> b10=: 10 typ 1+i.3e6 |
Task examples (base 10):<lang J> b10=: 10 typ 1+i.3e6 |
||
(9999 |
(9999&{, 50&{.)1+I._1=b10 NB. wasteful |
||
14346 |
14346 4 6 8 9 12 18 20 22 24 26 28 30 33 34 36 38 39 40 42 44 45 46 48 50 51 52 54 55 56 57 58 60 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 84 85 86 |
||
(9999 |
(9999&{, 50&{.)1+I. 0=b10 NB. equidigital |
||
33773 |
33773 2 3 5 7 10 11 13 14 15 16 17 19 21 23 25 27 29 31 32 35 37 41 43 47 49 53 59 61 64 67 71 73 79 81 83 89 97 101 103 105 106 107 109 111 112 113 115 118 119 121 |
||
(9999 |
(9999&{, 50&{.)1+I. 1=b10 NB. frugal |
||
1953031 |
1953031 1 125 128 243 256 343 512 625 729 1024 1029 1215 1250 1280 1331 1369 1458 1536 1681 1701 1715 1792 1849 1875 2048 2187 2197 2209 2401 2560 2809 3125 3481 3584 3645 3721 4096 4374 4375 4489 4802 4913 5041 5103 5329 6241 6250 6561 6859 6889 |
||
+/1e6>1+I._1=b10 NB. wasteful |
+/1e6>1+I._1=b10 NB. wasteful |
||
831231 |
831231 |
||
Line 68: | Line 68: | ||
+/1e6>1+I. 1=b10 NB. frugal |
+/1e6>1+I. 1=b10 NB. frugal |
||
3124</lang> |
3124</lang> |
||
It was not clear to me whether the 10000th was supposed to be the real 10000th (index 9999 in J) or the number after that (which would be the right answer if we were considering the unclassified value of 0 as being relevant). So.. here I show both. |
|||
Task examples (base 11):<lang J> b11=: 11 typ 1+i.3e6 |
Task examples (base 11):<lang J> b11=: 11 typ 1+i.3e6 |
||
(9999 |
(9999&{, 50&{.)1+I._1=b11 NB. wasteful |
||
12890 |
12890 4 6 8 9 10 12 18 20 22 24 26 28 30 33 34 36 38 39 40 42 44 45 46 48 50 51 52 54 55 56 57 58 60 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 84 85 |
||
(9999 |
(9999&{, 50&{.)1+I. 0=b11 NB. equidigital |
||
33207 |
33207 2 3 5 7 11 13 14 15 16 17 19 21 23 25 27 29 31 32 35 37 41 43 47 49 53 59 61 64 67 71 73 79 81 83 89 97 101 103 107 109 113 121 122 123 127 129 131 133 134 135 |
||
(9999 |
(9999&{, 50&{.)1+I. 1=b11 NB. frugal |
||
2658818 |
2658818 1 125 128 243 256 343 512 625 729 1024 1331 1369 1458 1536 1681 1701 1715 1792 1849 1875 2048 2187 2197 2209 2401 2560 2809 3072 3125 3481 3584 3645 3721 4096 4374 4375 4489 4802 4913 5041 5103 5120 5329 6241 6250 6561 6859 6889 7168 7203 |
||
+/1e6>1+I._1=b11 NB. wasteful |
+/1e6>1+I._1=b11 NB. wasteful |
||
795861 |
795861 |
Revision as of 11:32, 17 July 2022
- Definitions
Let n be a positive integer and l(n) be the number of its digits in base b.
Express n as the product of its prime factors raised to the appropriate powers. Let D(n) be the total number of its base b digits in all its prime factors and in all their exponents that are greater than 1.
Then n is defined to be:
1. a wasteful (or extravagant) number if l(n) < D(n); or
2. an equidigital number if l(n) = D(n); or
3. a frugal (or economical) number if l(n) > D(n)
in base b.
By convention, the number 1 is considered to be an equidigital number in any base even though it has no prime factors.
For the avoidance of any doubt, the number 0 is not a positive integer (and arguably not a natural number either) and so is excluded from all 3 categories.
An economical number is sometimes defined as being one for which l(n) >= D(n) though this usage won't be followed here.
- Examples
In base 10, the number 30 has a prime factorization of 2 x 3 x 5. The total number of digits is 3 (all exponents being 1) which is more than the 2 digits 30 has. So 30 is wasteful in base 10.
In base 10, the number 49 has a prime factorization of 7². The total number of digits, including those of the exponent, is 2 which is the same as the 2 digits 49 has. So 49 is equidigital in base 10.
In base 10, the number 125 has a prime factorization of 5³. The total number of digits, including those of the exponent, is 2 which is less than the 3 digits 125 has. So 125 is frugal in base 10.
In base 2, the number 100000 (32 decimal) has a prime factorization of 10^101 (2^5 decimal). The total number of binary digits, including those of the exponent, is 5 which is less than the 6 binary digits 100000 has. So 32 is frugal in base 2 (but equidigital in base 10).
- Task
Compute and show here the first 50 and the 10,000th number in base 10 for each of the three categories of number defined above.
Also compute and show how many numbers less than 1,000,000 fall into each of the three categories.
- Bonus
Do the same for base 11, but show the results in base 10.
- References
- OEIS: A046760 - Wasteful numbers
- OEIS: A046758 - Equidigital numbers
- OEIS: A046759 - Economical numbers
J
Brute force implementation:<lang J>I=: #@(#.inv)"0 D=: [ +/@:I __ (#~1<])@,@q: ] typ=: *@(I-D)"0 NB. _1: wasteful, 0: equidigital, 1: frugal</lang>
Task examples (base 10):<lang J> b10=: 10 typ 1+i.3e6
(9999&{, 50&{.)1+I._1=b10 NB. wasteful
14346 4 6 8 9 12 18 20 22 24 26 28 30 33 34 36 38 39 40 42 44 45 46 48 50 51 52 54 55 56 57 58 60 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 84 85 86
(9999&{, 50&{.)1+I. 0=b10 NB. equidigital
33773 2 3 5 7 10 11 13 14 15 16 17 19 21 23 25 27 29 31 32 35 37 41 43 47 49 53 59 61 64 67 71 73 79 81 83 89 97 101 103 105 106 107 109 111 112 113 115 118 119 121
(9999&{, 50&{.)1+I. 1=b10 NB. frugal
1953031 1 125 128 243 256 343 512 625 729 1024 1029 1215 1250 1280 1331 1369 1458 1536 1681 1701 1715 1792 1849 1875 2048 2187 2197 2209 2401 2560 2809 3125 3481 3584 3645 3721 4096 4374 4375 4489 4802 4913 5041 5103 5329 6241 6250 6561 6859 6889
+/1e6>1+I._1=b10 NB. wasteful
831231
+/1e6>1+I. 0=b10 NB. equidigital
165644
+/1e6>1+I. 1=b10 NB. frugal
3124</lang>
Task examples (base 11):<lang J> b11=: 11 typ 1+i.3e6
(9999&{, 50&{.)1+I._1=b11 NB. wasteful
12890 4 6 8 9 10 12 18 20 22 24 26 28 30 33 34 36 38 39 40 42 44 45 46 48 50 51 52 54 55 56 57 58 60 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 84 85
(9999&{, 50&{.)1+I. 0=b11 NB. equidigital
33207 2 3 5 7 11 13 14 15 16 17 19 21 23 25 27 29 31 32 35 37 41 43 47 49 53 59 61 64 67 71 73 79 81 83 89 97 101 103 107 109 113 121 122 123 127 129 131 133 134 135
(9999&{, 50&{.)1+I. 1=b11 NB. frugal
2658818 1 125 128 243 256 343 512 625 729 1024 1331 1369 1458 1536 1681 1701 1715 1792 1849 1875 2048 2187 2197 2209 2401 2560 2809 3072 3125 3481 3584 3645 3721 4096 4374 4375 4489 4802 4913 5041 5103 5120 5329 6241 6250 6561 6859 6889 7168 7203
+/1e6>1+I._1=b11 NB. wasteful
795861
+/1e6>1+I. 0=b11 NB. equidigital
200709
+/1e6>1+I. 1=b11 NB. frugal
3429</lang>
Julia
<lang ruby>using Primes
"""
function wastefulness(n, base = 10)
calculate d1: the number of digits in base `base` required to write the factor expansion of `n`, ie 12 -> 2^2 * 3^2 is 4 digits, 7 -> 7 is 1 digit, 20 -> 5 * 2^2 is 3 digits
calculate d2: the number of digits in base `base` to represent `n` itself
return -1 if frugal (d1 > d2), 0 if equidigital (d1 == d2), 1 if wasteful (d1 > d2) """ function wastefulness(n::Integer, base = 10)
@assert n > 0 return n == 1 ? 0 : sign(sum(p -> ndigits(p[1], base=base) + (p[2] == 1 ? 0 : ndigits(p[2], base=base)), factor(n).pe) - ndigits(n, base=base))
end
for b in [10, 11]
w50, e50, f50 = Int[], Int[], Int[] w10k, e10k, f10k, wcount, ecount, fcount, wm, em, fm = 0, 0, 0, 0, 0, 0, 0, 0, 0 for n in 1:10_000_000 sgn = wastefulness(n, b) if sgn < 0 fcount < 50 && push!(f50, n) fcount += 1 fcount == 10000 &&(f10k = n) n < 1_000_000 && (fm += 1) elseif sgn == 0 ecount < 50 && push!(e50, n) ecount += 1 ecount == 10000 && (e10k = n) n < 1_000_000 && (em += 1) else # sgn > 0 wcount < 50 && push!(w50, n) wcount += 1 wcount == 10000 && (w10k = n) n < 1_000_000 && (wm += 1) end if f10k > 0 println("FOR BASE $b:\n") println("First 50 Wasteful numbers:") foreach(p -> print(rpad(p[2], 5), p[1] % 10 == 0 ? "\n" : ""), pairs(w50)) println("\nFirst 50 Equidigital numbers:") foreach(p -> print(rpad(p[2], 5), p[1] % 10 == 0 ? "\n" : ""), pairs(e50)) println("\nFirst 50 Frugal numbers:") foreach(p -> print(rpad(p[2], 5), p[1] % 10 == 0 ? "\n" : ""), pairs(f50)) println("\n10,000th Wasteful number : $w10k") println("10,000th Equidigital number : $e10k") println("10,000th Frugal number : $f10k") println("\nFor natural numbers < 1 million, the breakdown is as follows:") println(" Wasteful numbers : $wm") println(" Equidigital numbers : $em") println(" Frugal numbers : $fm\n\n") break end end
end </lang> Output is the same as Wren example.
Phix
with javascript_semantics function analyze(integer n, b) sequence f = prime_factors(n,2,-1) integer digits = 0 for pq in f do integer {p,q} = pq digits += length(sprintf("%a",{{b,p}})) if q>1 then digits += length(sprintf("%a",{{b,q}})) end if end for -- -1/0/+1 => 1/2/3 for wasteful/equidigital/frugal: return compare(length(sprintf("%a",{{b,n}})), digits)+2 end function constant fmt = """ FOR BASE %d: First 50 Wasteful numbers: %s First 50 Equidigital numbers: %s First 50 Frugal numbers: %s 10,000th Wasteful number : %d 10,000th Equidigital number : %d 10,000th Frugal number : %d For natural numbers < 1 million, the breakdown is as follows: Wasteful numbers : %6d Equidigital numbers : %6d Frugal numbers : %6d """ for b in {10, 11} do sequence wef = {{},{1},{}}, w10k = {0,0,0}, c = {0,1,0}, c2 = {0,1,0} integer n = 2 atom t1 = time()+1 while min(c) < 10000 do integer wdx = analyze(n, b) if length(wef[wdx])<50 then wef[wdx] &= n elsif c[wdx]=9999 then w10k[wdx]=n end if c[wdx] += 1 if n<1e6 then c2[wdx] += 1 end if n += 1 if time()>t1 then progress("working %d...",{n}) t1 = time()+1 end if end while progress("") sequence w3 = apply(true,join_by,{wef,1,10,{" "},{"\n"},{"%4d"}}) printf(1,fmt,b&w3&w10k&c2) end for
Output identical to Wren
Raku
<lang perl6>use Prime::Factor; use Lingua::EN::Numbers;
sub frugal ($n, $base = 10) { ($n > 1) && $n.base($base).chars > sum $n.&prime-factors.Bag.map: { .key.base($base).chars + (.value > 1 ?? .value.base($base).chars !! 0) } } sub equidigital ($n, $base = 10) { ($n == 1) || $n.base($base).chars == sum $n.&prime-factors.Bag.map: { .key.base($base).chars + (.value > 1 ?? .value.base($base).chars !! 0) } } sub wasteful ($n, $base = 10) { $n.base($base).chars < sum $n.&prime-factors.Bag.map: { .key.base($base).chars + (.value > 1 ?? .value.base($base).chars !! 0) } }
for 10, 11 -> $base {
say "\nIn Base $base:"; for &wasteful, &equidigital, &frugal -> &sub { say "\nFirst 50 {&sub.name} numbers:"; say (^∞).grep( {.&sub($base)} )[^50].batch(10)».&comma».fmt("%6s").join: "\n"; say "10,000th: " ~ (^∞).hyper(:2000batch).grep( {.&sub($base)} )[9999]., }
my $upto = 1e6.Int; my atomicint ($Wasteful, $Equidigital, $Frugal); say "\nOf the positive integers up to {$upto.&cardinal} :"; (1..^$upto).race(:5000batch).map: { .&frugal($base) ?? ++⚛$Frugal !! .&equidigital($base) ?? ++⚛$Equidigital !! ++⚛$Wasteful }; say " Wasteful: {comma $Wasteful}\nEquidigital: {comma $Equidigital}\n Frugal: {comma $Frugal}";
}</lang>
- Output:
In Base 10: First 50 wasteful numbers: 4 6 8 9 12 18 20 22 24 26 28 30 33 34 36 38 39 40 42 44 45 46 48 50 51 52 54 55 56 57 58 60 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 84 85 86 10,000th: 14,346 First 50 equidigital numbers: 1 2 3 5 7 10 11 13 14 15 16 17 19 21 23 25 27 29 31 32 35 37 41 43 47 49 53 59 61 64 67 71 73 79 81 83 89 97 101 103 105 106 107 109 111 112 113 115 118 119 10,000th: 33,769 First 50 frugal numbers: 125 128 243 256 343 512 625 729 1,024 1,029 1,215 1,250 1,280 1,331 1,369 1,458 1,536 1,681 1,701 1,715 1,792 1,849 1,875 2,048 2,187 2,197 2,209 2,401 2,560 2,809 3,125 3,481 3,584 3,645 3,721 4,096 4,374 4,375 4,489 4,802 4,913 5,041 5,103 5,329 6,241 6,250 6,561 6,859 6,889 7,203 10,000th: 1,953,125 Of the positive integers up to one million : Wasteful: 831,231 Equidigital: 165,645 Frugal: 3,123 In Base 11: First 50 wasteful numbers: 4 6 8 9 10 12 18 20 22 24 26 28 30 33 34 36 38 39 40 42 44 45 46 48 50 51 52 54 55 56 57 58 60 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 84 85 10,000th: 12,890 First 50 equidigital numbers: 1 2 3 5 7 11 13 14 15 16 17 19 21 23 25 27 29 31 32 35 37 41 43 47 49 53 59 61 64 67 71 73 79 81 83 89 97 101 103 107 109 113 121 122 123 127 129 131 133 134 10,000th: 33,203 First 50 frugal numbers: 125 128 243 256 343 512 625 729 1,024 1,331 1,369 1,458 1,536 1,681 1,701 1,715 1,792 1,849 1,875 2,048 2,187 2,197 2,209 2,401 2,560 2,809 3,072 3,125 3,481 3,584 3,645 3,721 4,096 4,374 4,375 4,489 4,802 4,913 5,041 5,103 5,120 5,329 6,241 6,250 6,561 6,859 6,889 7,168 7,203 7,921 10,000th: 2,659,171 Of the positive integers up to one million : Wasteful: 795,861 Equidigital: 200,710 Frugal: 3,428
Wren
<lang ecmascript>import "./math" for Int import "./seq" for Lst import "./fmt" for Fmt
var analyze = Fn.new { |n, b|
var factors = Int.primeFactors(n) var indivs = Lst.individuals(factors) var digits = 0 for (indiv in indivs) { digits = digits + Int.digits(indiv[0], b).count if (indiv[1] > 1) digits = digits + Int.digits(indiv[1], b).count } return [Int.digits(n, b).count, digits]
}
for (b in [10, 11]) {
var w = [] var e = [1] var f = [] var wc = 0 var ec = 1 var fc = 0 var wc2 = 0 var ec2 = 1 var fc2 = 0 var n = 2 System.print("FOR BASE %(b):\n") while (fc < 10000 || ec < 10000 || wc < 10000) { var r = analyze.call(n, b) if (r[0] < r[1]) { if (w.count < 50 || wc == 9999) w.add(n) wc = wc + 1 if (n < 1e6) wc2 = wc2 + 1 } else if (r[0] == r[1]) { if (e.count < 50 || ec == 9999) e.add(n) ec = ec + 1 if (n < 1e6) ec2 = ec2 + 1 } else { if (f.count < 50 || fc == 9999) f.add(n) fc = fc + 1 if (n < 1e6) fc2 = fc2 + 1 } n = n + 1 } System.print("First 50 Wasteful numbers:") Fmt.tprint("$4d", w[0..49], 10) System.print() System.print("First 50 Equidigital numbers:") Fmt.tprint("$4d", e[0..49], 10) System.print() System.print("First 50 Frugal numbers:") Fmt.tprint("$4d", f[0..49], 10) System.print() System.print("10,000th Wasteful number : %(w[50])") System.print("10,000th Equidigital number : %(e[50])") System.print("10,000th Frugal number : %(f[50])") System.print() System.print("For natural numbers < 1 million, the breakdown is as follows:") Fmt.print(" Wasteful numbers : $6d", wc2) Fmt.print(" Equidigital numbers : $6d", ec2) Fmt.print(" Frugal numbers : $6d", fc2) System.print()
}</lang>
- Output:
FOR BASE 10: First 50 Wasteful numbers: 4 6 8 9 12 18 20 22 24 26 28 30 33 34 36 38 39 40 42 44 45 46 48 50 51 52 54 55 56 57 58 60 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 84 85 86 First 50 Equidigital numbers: 1 2 3 5 7 10 11 13 14 15 16 17 19 21 23 25 27 29 31 32 35 37 41 43 47 49 53 59 61 64 67 71 73 79 81 83 89 97 101 103 105 106 107 109 111 112 113 115 118 119 First 50 Frugal numbers: 125 128 243 256 343 512 625 729 1024 1029 1215 1250 1280 1331 1369 1458 1536 1681 1701 1715 1792 1849 1875 2048 2187 2197 2209 2401 2560 2809 3125 3481 3584 3645 3721 4096 4374 4375 4489 4802 4913 5041 5103 5329 6241 6250 6561 6859 6889 7203 10,000th Wasteful number : 14346 10,000th Equidigital number : 33769 10,000th Frugal number : 1953125 For natural numbers < 1 million, the breakdown is as follows: Wasteful numbers : 831231 Equidigital numbers : 165645 Frugal numbers : 3123 FOR BASE 11: First 50 Wasteful numbers: 4 6 8 9 10 12 18 20 22 24 26 28 30 33 34 36 38 39 40 42 44 45 46 48 50 51 52 54 55 56 57 58 60 62 63 65 66 68 69 70 72 74 75 76 77 78 80 82 84 85 First 50 Equidigital numbers: 1 2 3 5 7 11 13 14 15 16 17 19 21 23 25 27 29 31 32 35 37 41 43 47 49 53 59 61 64 67 71 73 79 81 83 89 97 101 103 107 109 113 121 122 123 127 129 131 133 134 First 50 Frugal numbers: 125 128 243 256 343 512 625 729 1024 1331 1369 1458 1536 1681 1701 1715 1792 1849 1875 2048 2187 2197 2209 2401 2560 2809 3072 3125 3481 3584 3645 3721 4096 4374 4375 4489 4802 4913 5041 5103 5120 5329 6241 6250 6561 6859 6889 7168 7203 7921 10,000th Wasteful number : 12890 10,000th Equidigital number : 33203 10,000th Frugal number : 2659171 For natural numbers < 1 million, the breakdown is as follows: Wasteful numbers : 795861 Equidigital numbers : 200710 Frugal numbers : 3428