Duffinian numbers: Difference between revisions
(Added Wren) |
(→{{header|Wren}}: Simpler.) |
||
Line 122: | Line 122: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-set}} |
|||
{{libheader|Wren-seq}} |
{{libheader|Wren-seq}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
<lang ecmascript>import "./math" for Int, Nums |
<lang ecmascript>import "./math" for Int, Nums |
||
import "./set" for Set |
|||
import "./seq" for Lst |
import "./seq" for Lst |
||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
Line 140: | Line 138: | ||
} |
} |
||
var sigmaSum = Nums.sum(Int.divisors(i)) |
var sigmaSum = Nums.sum(Int.divisors(i)) |
||
if (Int.gcd(sigmaSum, i) != 1) d[i] = false |
|||
if (set.containsAny(Int.primeFactors(i))) d[i] = false |
|||
} |
} |
||
Revision as of 10:06, 25 February 2022
A Duffinian number is a composite number k that is relatively prime to its sigma sum σ.
The sigma sum of k is the sum of the divisors of k.
- E.G.
161 is a Duffinian number.
- It is composite. (7 × 23)
- The sigma sum 192 (1 + 7 + 23 + 161) is relatively prime to 161.
Duffinian numbers are very common.
It is not uncommon for two consecutive integers to be Duffinian (a Duffinian twin) (8, 9), (35, 36), (49, 50), etc.
Less common are Duffinian triplets; three consecutive Duffinian numbers. (63, 64, 65), (323, 324, 325), etc.
Much, much less common are Duffinian quadruplets and quintuplets. The first Duffinian quintuplet is (202605639573839041, 202605639573839042, 202605639573839043, 202605639573839044, 202605639573839045).
It is not possible to have six consecutive Duffinian numbers
- Task
- Find and show the first 50 Duffinian numbers.
- Find and show at least the first 15 Duffinian triplets.
- See also
Julia
<lang julia>using Primes
function σ(n)
f = [one(n)] for (p,e) in factor(n) f = reduce(vcat, [f*p^j for j in 1:e], init=f) end return sum(f)
end
isDuffinian(n) = !isprime(n) && gcd(n, σ(n)) == 1
function testDuffinians()
println("First 50 Duffinian numbers:") foreach(p -> print(rpad(p[2], 4), p[1] % 25 == 0 ? "\n" : ""), enumerate(filter(isDuffinian, 2:217))) n, found = 2, 0 println("\nFifteen Duffinian triplets:") while found < 15 if isDuffinian(n) && isDuffinian(n + 1) && isDuffinian(n + 2) println(lpad(n, 6), lpad(n +1, 6), lpad(n + 2, 6)) found += 1 end n += 1 end
end
testDuffinians()
</lang>
- Output:
First 50 Duffinian numbers: 4 8 9 16 21 25 27 32 35 36 39 49 50 55 57 63 64 65 75 77 81 85 93 98 100 111 115 119 121 125 128 129 133 143 144 155 161 169 171 175 183 185 187 189 201 203 205 209 215 217 Fifteen Duffinian triplets: 63 64 65 323 324 325 511 512 513 721 722 723 899 900 901 1443 1444 1445 2303 2304 2305 2449 2450 2451 3599 3600 3601 3871 3872 3873 5183 5184 5185 5617 5618 5619 6049 6050 6051 6399 6400 6401 8449 8450 8451
Raku
<lang perl6>use Prime::Factor;
my @duffinians = lazy (3..*).hyper.grep: { !.is-prime && $_ gcd .&divisors.sum == 1 };
put "First 50 Duffinian numbers:\n" ~ @duffinians[^50].batch(10)».fmt("%3d").join: "\n";
put "\nFirst 40 Duffinian triplets:\n" ~
((^∞).grep: -> $n { (@duffinians[$n] + 1 == @duffinians[$n + 1]) && (@duffinians[$n] + 2 == @duffinians[$n + 2]) })[^40]\ .map( { "({@duffinians[$_ .. $_+2].join: ', '})" } ).batch(4)».fmt("%-24s").join: "\n";</lang>
- Output:
First 50 Duffinian numbers: 4 8 9 16 21 25 27 32 35 36 39 49 50 55 57 63 64 65 75 77 81 85 93 98 100 111 115 119 121 125 128 129 133 143 144 155 161 169 171 175 183 185 187 189 201 203 205 209 215 217 First 40 Duffinian triplets: (63, 64, 65) (323, 324, 325) (511, 512, 513) (721, 722, 723) (899, 900, 901) (1443, 1444, 1445) (2303, 2304, 2305) (2449, 2450, 2451) (3599, 3600, 3601) (3871, 3872, 3873) (5183, 5184, 5185) (5617, 5618, 5619) (6049, 6050, 6051) (6399, 6400, 6401) (8449, 8450, 8451) (10081, 10082, 10083) (10403, 10404, 10405) (11663, 11664, 11665) (12481, 12482, 12483) (13447, 13448, 13449) (13777, 13778, 13779) (15841, 15842, 15843) (17423, 17424, 17425) (19043, 19044, 19045) (26911, 26912, 26913) (30275, 30276, 30277) (36863, 36864, 36865) (42631, 42632, 42633) (46655, 46656, 46657) (47523, 47524, 47525) (53137, 53138, 53139) (58563, 58564, 58565) (72961, 72962, 72963) (76175, 76176, 76177) (79523, 79524, 79525) (84099, 84100, 84101) (86527, 86528, 86529) (94177, 94178, 94179) (108899, 108900, 108901) (121103, 121104, 121105)
Wren
<lang ecmascript>import "./math" for Int, Nums import "./seq" for Lst import "./fmt" for Fmt
var limit = 200000 // say var d = Int.primeSieve(limit-1, false) d[1] = false for (i in 2...limit) {
if (!d[i]) continue if (i % 2 == 0 && !Int.isSquare(i) && !Int.isSquare(i/2)) { d[i] = false continue } var sigmaSum = Nums.sum(Int.divisors(i)) if (Int.gcd(sigmaSum, i) != 1) d[i] = false
}
var duff = (1...d.count).where { |i| d[i] }.toList System.print("First 50 Duffinian numbers:") for (chunk in Lst.chunks(duff[0..49], 10)) Fmt.print("$3d", chunk)
var triplets = [] for (i in 2...limit) {
if (d[i] && d[i-1] && d[i-2]) triplets.add([i-2, i-1, i])
} System.print("\nFirst 50 Duffinian triplets:") for (chunk in Lst.chunks(triplets[0..49], 4)) Fmt.print("$-25s", chunk)</lang>
- Output:
First 50 Duffinian numbers: 4 8 9 16 21 25 27 32 35 36 39 49 50 55 57 63 64 65 75 77 81 85 93 98 100 111 115 119 121 125 128 129 133 143 144 155 161 169 171 175 183 185 187 189 201 203 205 209 215 217 First 50 Duffinian triplets: [63, 64, 65] [323, 324, 325] [511, 512, 513] [721, 722, 723] [899, 900, 901] [1443, 1444, 1445] [2303, 2304, 2305] [2449, 2450, 2451] [3599, 3600, 3601] [3871, 3872, 3873] [5183, 5184, 5185] [5617, 5618, 5619] [6049, 6050, 6051] [6399, 6400, 6401] [8449, 8450, 8451] [10081, 10082, 10083] [10403, 10404, 10405] [11663, 11664, 11665] [12481, 12482, 12483] [13447, 13448, 13449] [13777, 13778, 13779] [15841, 15842, 15843] [17423, 17424, 17425] [19043, 19044, 19045] [26911, 26912, 26913] [30275, 30276, 30277] [36863, 36864, 36865] [42631, 42632, 42633] [46655, 46656, 46657] [47523, 47524, 47525] [53137, 53138, 53139] [58563, 58564, 58565] [72961, 72962, 72963] [76175, 76176, 76177] [79523, 79524, 79525] [84099, 84100, 84101] [86527, 86528, 86529] [94177, 94178, 94179] [108899, 108900, 108901] [121103, 121104, 121105] [125315, 125316, 125317] [128017, 128018, 128019] [129599, 129600, 129601] [137287, 137288, 137289] [144399, 144400, 144401] [144721, 144722, 144723] [154567, 154568, 154569] [158403, 158404, 158405] [166463, 166464, 166465] [167041, 167042, 167043]