The Weekly Challenge 041

Attractive Numbers and Leonardo Numbers

Solutions on GitHub

Task 1: Attractive Numbers

Write a script to display attractive numbers between 1 and 50. An attractive number is a positive integer whose number of prime factors (with multiplicity) is a prime number.

Example Output

Attractive numbers: 4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28, 32, 36, 40, 44, 45, 48, 49, 50

Logic

Compute the prime factors of each number. Sum the multiplicities of these factors to find the count of prime factors. Check if this count is a prime number. If it is, the number is attractive.

Perl Solution

ch-1.pl

use Math::Factor::XS qw/count_prime_factors/; use Math::Prime::XS qw/is_prime/; sub is_attractive { my $what = shift; return is_prime(count_prime_factors($what)); }

Python Solution

ch-1.py

from sympy.ntheory import factorint, isprime def is_attractive(what): factors = factorint(int(what)) return isprime(sum(factors.values()))

Task 2: Leonardo Numbers

Write a script to display the first 20 Leonardo Numbers.

Example Output

1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973, 3193, 5167, 8361, 13529

Logic

Leonardo numbers are defined recursively as: L(0) = 1, L(1) = 1, and L(n) = L(n-1) + L(n-2) + 1 for n >= 2.

Perl Solution

ch-2.pl

my @l = (1,1); for (2..19) { $l[$_] = $l[$_-2] + $l[$_-1]+1; }

Python Solution

ch-2.py

l = [1,1] for i in range(2,20): l.append(l[i-2]+l[i-1]+1) print(l)