Achilles numbers: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|Wren}}: Removed a blank line.)
m (→‎{{header|Raku}}: avoid unnecessary caching, remove some recalculations)
Line 183: Line 183:
}
}


my @achilles = powerful(10**5).sort.hyper.grep: {
my $achilles = powerful(10**9).hyper(:500batch).grep( {
my $f = .&prime-factors.Bag;
my $f = .&prime-factors.Bag;
(+$f.keys > 1) && (1 == [gcd] $f.values) && (.sqrt.Int² !== $_)
(+$f.keys > 1) && (1 == [gcd] $f.values) && (.sqrt.Int² !== $_)
⚫
} ).classify: { .chars }
};


my \𝜑 = 0, |(1..*).hyper.map: -> \t { t × [×] t.&prime-factors.squish.map: { 1 - 1/$_ } }
my \𝜑 = 0, |(1..*).hyper.map: -> \t { t × [×] t.&prime-factors.squish.map: { 1 - 1/$_ } }


my %ps = Set.new: @achilles;
my %as = Set.new: flat $achilles.values».list;


my @strong = @achilles.grep: { ?%ps{𝜑[$_]} };
my $strong = lazy (flat $achilles.sort».value».list».sort).grep: { ?%as{𝜑[$_]} };


put "First 50 Achilles numbers:";
put "First 50 Achilles numbers:";
put @achilles[^50].batch(10)».fmt("%4d").join("\n");
put (flat $achilles.sort».value».list».sort)[^50].batch(10)».fmt("%4d").join("\n");


put "\nFirst 30 strong Achilles numbers:";
put "\nFirst 30 strong Achilles numbers:";
put @strong[^30].batch(10)».fmt("%5d").join("\n");
put $strong[^30].batch(10)».fmt("%5d").join("\n");

my $achilles = powerful(10**9).hyper(:500batch).grep( {
my $f = .&prime-factors.Bag;
(+$f.keys > 1) && (1 == [gcd] $f.values) && (.sqrt.Int² !== $_)
⚫
} ).classify: { .chars }


put "\nNumber of Achilles numbers with:";
put "\nNumber of Achilles numbers with:";

Revision as of 14:48, 26 February 2022

Achilles 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.
This page uses content from Wikipedia. The original article was at Achilles number. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)


An Achilles number is a number that is powerful but imperfect. Named after Achilles, a hero of the Trojan war, who was also powerful but imperfect.


A positive integer n is a powerful number if, for every prime factor p of n, p2 is also a divisor.

In other words, every prime factor appears at least squared in the factorization.

All Achilles numbers are powerful. However, not all powerful numbers are Achilles numbers: only those that cannot be represented as mk, where m and k are positive integers greater than 1.


A strong Achilles number is an Achilles number whose Euler totient (𝜑) is also an Achilles number.


E.G.

108 is a powerful number. Its prime factorization is 22 × 33, and thus its prime factors are 2 and 3. Both 22 = 4 and 32 = 9 are divisors of 108. However, 108 cannot be represented as mk, where m and k are positive integers greater than 1, so 108 is an Achilles number.

360 is not an Achilles number because it is not powerful. One of its prime factors is 5 but 360 is not divisible by 52 = 25.

Finally, 784 is not an Achilles number. It is a powerful number, because not only are 2 and 7 its only prime factors, but also 22 = 4 and 72 = 49 are divisors of it. Nonetheless, it is a perfect power; its square root is an even integer, so it is not an Achilles number.


500 = 22 × 53 is a strong Achilles number as its Euler totient, 𝜑(500), is 200 = 23 × 52 which is also an Achilles number.


Task
  • Find and show the first 50 Achilles numbers.
  • Find and show at least the first 20 strong Achilles numbers.
  • For at least 2 through 5, show the count of Achilles numbers with that many digits.


See also



J

Implementation:

<lang J>achilles=: (*/ .>&1 * 1 = +./)@(1{__&q:)"0 strong=: achilles@(5&p:)</lang>

Task examples:

<lang J> 5 10$(#~ achilles) 1+i.10000 NB. first 50 achilles numbers 

 72  108  200  288  392  432  500  648  675  800
864  968  972 1125 1152 1323 1352 1372 1568 1800

1944 2000 2312 2592 2700 2888 3087 3200 3267 3456 3528 3872 3888 4000 4232 4500 4563 4608 5000 5292 5324 5400 5408 5488 6075 6125 6272 6728 6912 7200 

  20{.(#~ strong * achilles) 1+i.100000 NB. first twenty strong achilles numbers

500 864 1944 2000 2592 3456 5000 10125 10368 12348 12500 16875 19652 19773 30375 31104 32000 33275 37044 40500 

  +/achilles (+i.)/1 9*10^<:2  NB. count of two digit achilles numbers

1 

  +/achilles (+i.)/1 9*10^<:3

12 

  +/achilles (+i.)/1 9*10^<:4

47 

  +/achilles (+i.)/1 9*10^<:5

192 

  +/achilles (+i.)/1 9*10^<:6

664</lang>

Explanation of the code:

(1{__&q:) is a function which returns the non-zero powers of the prime factors of a positive integer. (__&q: returns both the primes and their factors, but here we do not care about the primes themselves.)

+./ returns the greatest common divisor of a list, and 1=+./ is true if that gcd is 1 (0 if it's false).

*/ .>&1 is true if all the values in a list are greater than 1 (0 if not).

"0 maps a function onto the individual (rank 0) items of a list or array (we use this to avoid complexities: for example if we padded our lists of prime factor powers with zeros, we could still find the gcd, but our test that the powers are greater than 1 would fail).

5&p: is euler's totient function.

(#~ predicate) list selects the elements of list where predicate is true.

Julia

<lang>using Primes

isAchilles(n) = (p = [x[2] for x in factor(n).pe]; all(>(1), p) && gcd(p) == 1)

isstrongAchilles(n) = isAchilles(n) && isAchilles(totient(n))

function teststrongachilles(nachilles = 50, nstrongachilles = 100) 

   # task 1
   println("First $nachilles Achilles numbers:")
   n, found = 0, 0
   while found < nachilles
       if isAchilles(n)
           found += 1
           print(rpad(n, 5), found % 10 == 0 ? "\n" : "")
       end
       n += 1
   end
   # task 2
   println("\nFirst $nstrongachilles strong Achilles numbers:")
   n, found = 0, 0
   while found < nstrongachilles
       if isstrongAchilles(n)
           found += 1
           print(rpad(n, 7), found % 10 == 0 ? "\n" : "")
       end
       n += 1
   end
   # task 3
   println("\nCount of Achilles numbers for various intervals:")
   intervals = [10:99, 100:999, 1000:9999, 10000:99999, 100000:999999]
   for interval in intervals
       println(lpad(interval, 15), " ", count(isAchilles, interval))
   end

end

teststrongachilles()

</lang>

Output:
First 50 Achilles numbers:
72   108  200  288  392  432  500  648  675  800
864  968  972  1125 1152 1323 1352 1372 1568 1800
1944 2000 2312 2592 2700 2888 3087 3200 3267 3456
3528 3872 3888 4000 4232 4500 4563 4608 5000 5292
5324 5400 5408 5488 6075 6125 6272 6728 6912 7200

First 100 strong Achilles numbers:
500    864    1944   2000   2592   3456   5000   10125  10368  12348
12500  16875  19652  19773  30375  31104  32000  33275  37044  40500  
49392  50000  52488  55296  61731  64827  67500  69984  78608  80000  
81000  83349  84375  93312  108000 111132 124416 128000 135000 148176 
151875 158184 162000 165888 172872 177957 197568 200000 202612 209952 
219488 221184 237276 243000 246924 253125 266200 270000 273375 296352 
320000 324000 333396 364500 397953 405000 432000 444528 453789 455877 
493848 497664 500000 518616 533871 540000 555579 583443 605052 607500 
629856 632736 648000 663552 665500 666792 675000 691488 740772 750141 
790272 800000 810448 820125 831875 877952 949104 972000 987696 1000188

Count of Achilles numbers for various intervals:
          10:99 1
        100:999 12
      1000:9999 47
    10000:99999 192
  100000:999999 664

Raku

<lang perl6>use Prime::Factor; use Math::Root;

sub is-square-free (Int \n) { 

   constant @p = ^100 .map: { next unless .is-prime; .² };
   for @p -> \p { return False if n %% p }
   True

}

sub powerful (\n, \k = 2) { 

   my @p;
   p(1, 2*k - 1);
   sub p (\m, \r) {
       @p.push(m) and return if r < k;
       for 1 .. (n / m).&root(r) -> \v {
           if r > k {
               next unless is-square-free(v);
               next unless m gcd v == 1;
           }
           p(m * v ** r, r - 1)
       }
   }
   @p

}

my $achilles = powerful(10**9).hyper(:500batch).grep( { 

   my $f = .&prime-factors.Bag;
   (+$f.keys > 1) && (1 == [gcd] $f.values) && (.sqrt.Int² !== $_)

} ).classify: { .chars }

my \𝜑 = 0, |(1..*).hyper.map: -> \t { t × [×] t.&prime-factors.squish.map: { 1 - 1/$_ } }

my %as = Set.new: flat $achilles.values».list;

my $strong = lazy (flat $achilles.sort».value».list».sort).grep: { ?%as{𝜑[$_]} };

put "First 50 Achilles numbers:"; put (flat $achilles.sort».value».list».sort)[^50].batch(10)».fmt("%4d").join("\n");

put "\nFirst 30 strong Achilles numbers:"; put $strong[^30].batch(10)».fmt("%5d").join("\n");

put "\nNumber of Achilles numbers with:"; say "$_ digits: " ~ +$achilles{$_} // 0 for 2..9;</lang>

Output:
First 50 Achilles numbers:
  72  108  200  288  392  432  500  648  675  800
 864  968  972 1125 1152 1323 1352 1372 1568 1800
1944 2000 2312 2592 2700 2888 3087 3200 3267 3456
3528 3872 3888 4000 4232 4500 4563 4608 5000 5292
5324 5400 5408 5488 6075 6125 6272 6728 6912 7200

First 30 strong Achilles numbers:
  500   864  1944  2000  2592  3456  5000 10125 10368 12348
12500 16875 19652 19773 30375 31104 32000 33275 37044 40500
49392 50000 52488 55296 61731 64827 67500 69984 78608 80000

Number of Achilles numbers with:
2 digits: 1
3 digits: 12
4 digits: 47
5 digits: 192
6 digits: 664
7 digits: 2242
8 digits: 7395
9 digits: 24008

Wren

Library: Wren-math
Library: Wren-seq
Library: Wren-fmt

This finds the number of 6 digit Achilles numbers in 2.5 seconds, 7 digits in 51 seconds but 8 digits needs a whopping 21 minutes! <lang ecmascript>import "./math" for Int import "./seq" for Lst import "./fmt" for Fmt

var maxDigits = 8 var limit = 10.pow(maxDigits) var c = Int.primeSieve(limit-1, false)

var totient = Fn.new { |n| 

   var tot = n
   var i = 2
   while (i*i <= n) {
       if (n%i == 0) {
           while(n%i == 0) n = (n/i).floor
           tot = tot - (tot/i).floor
       }
       if (i == 2) i = 1
       i = i + 2
   }
   if (n > 1) tot = tot - (tot/n).floor
   return tot

}

var isPerfectPower = Fn.new { |n| 

   if (n == 1) return true
   var x = 2
   while (x * x <= n) {
       var y = 2
       var p = x.pow(y)
       while (p > 0 && p <= n) {
           if (p == n) return true
           y = y + 1
           p = x.pow(y)
       }
       x = x + 1
   }
   return false

}

var isPowerful = Fn.new { |n| 

   while (n % 2 == 0) {
       var p = 0
       while (n % 2 == 0) {
           n = (n/2).floor
           p = p + 1
       }
       if (p == 1) return false
   }
   var f = 3
   while (f * f <= n) {
       var p = 0
       while (n % f == 0) {
           n = (n/f).floor
           p = p + 1
       }
       if (p == 1) return false
       f = f + 2
   }
   return n == 1

}

var isAchilles = Fn.new { |n| c[n] && isPowerful.call(n) && !isPerfectPower.call(n) }

var isStrongAchilles = Fn.new { |n| 

   if (!isAchilles.call(n)) return false
   var tot = totient.call(n)
   return isAchilles.call(tot)

}

System.print("First 50 Achilles numbers:") var achilles = [] var count = 0 var n = 2 while (count < 50) { 

   if (isAchilles.call(n)) {
       achilles.add(n)
       count = count + 1
   }
   n = n + 1

} for (chunk in Lst.chunks(achilles, 10)) Fmt.print("$4d", chunk)

System.print("\nFirst 30 strong Achilles numbers:") var strongAchilles = [] count = 0 n = achilles[0] while (count < 30) { 

   if (isStrongAchilles.call(n)) {
       strongAchilles.add(n)
       count = count + 1
   }
   n = n + 1

} for (chunk in Lst.chunks(strongAchilles, 10)) Fmt.print("$5d", chunk)

System.print("\nNumber of Achilles numbers with:") var pow = 10 for (i in 2..maxDigits) { 

   var count = 0
   for (j in pow..pow*10-1) {
       if (isAchilles.call(j)) count = count + 1
   }
   System.print("%(i) digits: %(count)")
   pow = pow * 10

}</lang>

Output:
First 50 Achilles numbers:
  72  108  200  288  392  432  500  648  675  800
 864  968  972 1125 1152 1323 1352 1372 1568 1800
1944 2000 2312 2592 2700 2888 3087 3200 3267 3456
3528 3872 3888 4000 4232 4500 4563 4608 5000 5292
5324 5400 5408 5488 6075 6125 6272 6728 6912 7200

First 30 strong Achilles numbers:
  500   864  1944  2000  2592  3456  5000 10125 10368 12348
12500 16875 19652 19773 30375 31104 32000 33275 37044 40500
49392 50000 52488 55296 61731 64827 67500 69984 78608 80000

Number of Achilles numbers with:
2 digits: 1
3 digits: 12
4 digits: 47
5 digits: 192
6 digits: 664
7 digits: 2242
8 digits: 7395
Retrieved from "https://rosettacode.org/wiki/Achilles_numbers?oldid=319970"