Giuga numbers: Difference between revisions
(Added XPL0 example.) |
(Added Go) |
||
Line 25: | Line 25: | ||
<br><br> |
<br><br> |
||
=={{header|Go}}== |
|||
{{trans|Wren}} |
|||
{{libheader|Go-rcu}} |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"rcu" |
|||
) |
|||
func main() { |
|||
const limit = 4 |
|||
var giuga []int |
|||
for n := 4; len(giuga) < limit; n += 2 { |
|||
factors := rcu.PrimeFactors(n) |
|||
if len(factors) > 2 { |
|||
isSquareFree := true |
|||
for i := 1; i < len(factors); i++ { |
|||
if factors[i] == factors[i-1] { |
|||
isSquareFree = false |
|||
break |
|||
} |
|||
} |
|||
if isSquareFree { |
|||
isGiuga := true |
|||
for _, f := range factors { |
|||
if (n/f-1)%f != 0 { |
|||
isGiuga = false |
|||
break |
|||
} |
|||
} |
|||
if isGiuga { |
|||
giuga = append(giuga, n) |
|||
} |
|||
} |
|||
} |
|||
} |
|||
fmt.Println("The first", limit, "Giuga numbers are:") |
|||
fmt.Println(giuga) |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
The first 4 Giuga numbers are: |
|||
[30 858 1722 66198] |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |
Revision as of 08:41, 2 July 2022
- Definition
A Giuga number is a composite number n which is such that each of its distinct prime factors f divide (n/f - 1) exactly.
All known Giuga numbers are even though it is not known for certain that there are no odd examples.
- Example
30 is a Giuga number because its distinct prime factors are 2, 3 and 5 and:
- 30/2 - 1 = 14 is divisible by 2
- 30/3 - 1 = 9 is divisible by 3
- 30/5 - 1 = 5 is divisible by 5
- Task
Determine and show here the first four Giuga numbers.
- Stretch
Determine the fifth Giuga number and any more you have the patience for.
- References
Go
<lang go>package main
import (
"fmt" "rcu"
)
func main() {
const limit = 4 var giuga []int for n := 4; len(giuga) < limit; n += 2 { factors := rcu.PrimeFactors(n) if len(factors) > 2 { isSquareFree := true for i := 1; i < len(factors); i++ { if factors[i] == factors[i-1] { isSquareFree = false break } } if isSquareFree { isGiuga := true for _, f := range factors { if (n/f-1)%f != 0 { isGiuga = false break } } if isGiuga { giuga = append(giuga, n) } } } } fmt.Println("The first", limit, "Giuga numbers are:") fmt.Println(giuga)
}</lang>
- Output:
The first 4 Giuga numbers are: [30 858 1722 66198]
Julia
<lang ruby>using Primes
isGiuga(n) = all(f -> f != n && rem(n ÷ f - 1, f) == 0, factor(Vector, n))
function getGiuga(N)
gcount = 0 for i in 4:typemax(Int) if isGiuga(i) println(i) (gcount += 1) >= N && break end end
end
getGiuga(4)
</lang>
- Output:
30 858 1722 66198
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Giuga_numbers use warnings; use ntheory qw( factor forcomposites ); use List::Util qw( all );
forcomposites
{ my $n = $_; all { ($n / $_ - 1) % $_ == 0 } factor $n and print "$n\n"; } 4, 67000;</lang>
- Output:
30 858 1722 66198
Wren
Simple brute force but assumes all Giuga numbers will be even, must be square-free and can't be semi-prime.
Takes only about 0.1 seconds to find the first four Giuga numbers but finding the fifth would take many hours using this approach, so I haven't bothered. Hopefully, someone can come up with a better method. <lang ecmascript>import "./math" for Int import "./seq" for Lst
var limit = 4 var giuga = [] var n = 4 while (giuga.count < limit) {
var factors = Int.primeFactors(n) var c = factors.count if (c > 2) { var factors2 = Lst.prune(factors) if (c == factors2.count && factors2.all { |f| (n/f - 1) % f == 0 }) { giuga.add(n) } } n = n + 2
} System.print("The first %(limit) Giuga numbers are:") System.print(giuga)</lang>
- Output:
The first 4 Giuga numbers are: [30, 858, 1722, 66198]
XPL0
<lang XPL0>func Giuga(N0); \Return 'true' if Giuga number int N0; int N, F, Q1, Q2, L; [N:= N0; F:= 2; L:= sqrt(N); loop [Q1:= N/F;
if rem(0) = 0 then \found a prime factor [Q2:= N0/F; if rem((Q2-1)/F) # 0 then return false; N:= Q1; if F>N then quit; ] else [F:= F+1; if F>L then return false; ]; ];
return true; ];
int N, C; [N:= 3; C:= 0; loop [if Giuga(N) then
[IntOut(0, N); ChOut(0, ^ ); C:= C+1; if C >= 4 then quit; ]; N:= N+1; ];
]</lang>
- Output:
30 858 1722 66198