Count how many numbers are divisible by perfect numbers in a given range

Question

Given two arbitrary integers \$a\$ and \$b\$, count how many numbers are divisible by perfect numbers in that given range (\$a\$ and \$b\$ both are inclusive).

In mathematics, a perfect number is a positive integer that is the sum of its proper positive divisors, that is, the sum of the positive divisors excluding the number itself.Equivalently, a perfect number is a number that is half the sum of all of its positive divisors (including itself), or \$σ(n) = 2n\$.

Input:

1 100

Output:

18

• Use stdin and stdout for Input/Output
• Your code must handle big integers, so it is not good enough to hard-code a list of perfect numbers.
• Shortest code wins

Answer 1

Perl 6, 106 103 characters

my ($a,$b)=get.words;(($a..$b).grep: *%%any ($a..$b).grep: {$^n==[+] ($^n%%$_&&$_ for 1..^$^n)})[*.say]

There's a lot of syntax here, so hopefully this explanation helps at least a little to someone who knows a bit of Perl 5 syntax, though I won't explain every detail:

Finds all the perfect numbers in the range $a..$b: ($a..$b).grep: {$^n==[+] ($^n%%$_&&$_ for 1..^$^n)} (explained below). It then chooses all the numbers in the range $a..$b which are divisible (%%) by any of the perfect numbers it had found: (%a..%b).grep: * %% any ….

The final (…)[*.say] abuses the fact that any code (in this case *.say, which prints its argument and a newline) passed to the […] postfix will be given the list's length as its argument (so that one can, e.g., use the idiomatic @array[*-1] to get the last element of @array). This means that the (…)[*.say] here has the same effect as say (…).elems.

The part that finds all the perfect numbers in the range does so by returning only those numbers which are equal ($^n ==) to the sum of their divisors. [+] adds together the values following it, for 1..^$^n iterates over all numbers 1 to $^n-1 and assigns $_ to them, and $^n %% $_ && $_ returns $_ if $^n is divisible ($^n %% $_) by $_, or else False, thus creating a list that consists of the proper divisors of $^n and False objects, which numify to 0 when all the values are added together by [+].

Perl 6 uses arbitrary sized integers, so, if you have the resources and the time, it could technically compute for big integers

Answer 2

Mathematica - 117

Naive approach, linear for the range size

With[{p=#(#+1)/2&/@Select[2^Range@@Floor@Log2@Sqrt@#-1,PrimeQ]},Length@Select[Range@@#,Or@@Divisible[#,p]&]]&@Input[]

The correct way would be constructing numbers from the perfect numbers that are in the given range of course.

Answer 3

Haskell - 157

c x=x==sum[i|i<-[1..x-1],mod x i==0]
d x=any((0==).mod x)$takeWhile(<=x)(filter c[2..])
main=do m<-getLine;n<-getLine;print$length(filter d[read m..read n])

Can work with arbitrarily large numbers given respectively large time.
Input is given on 2 lines.

Answer 4

C, 125120

a,b,c,p[4]={6,28,496,8128};main(i){for(scanf("%d%d",&a,&b);a<=b;a++)for(i=0;i<4;)if(a%p[i++]==0)c++,i=4;printf("%d",c);}

A little more readable:

a,b,c=0,i,p[4]={6,28,496,8128};
main()
{
    for(scanf("%d%d",&a,&b);a<=b;a++)
        for(i=0;i<4;)
            if(a%p[i++]==0)
            {
                c++;
                i=4;
            }
    printf("%d",c);
}

This works with signed 32bit integers, up to 2^31-1=2147483647.

C, 212209

#include<stdint.h>
uint64_t a,b,c,p[8]={6,28,496,8128,33550336,8589869056,137438691328,0x1fffffffc0000000};main(i){for(scanf("%lld%lld",&a,&b);a<=b;a++)for(i=0;i<8;)if(a%p[i++]==0)c++,i=8;printf("%lld",c);}

Should work up to 2^64-1=18446744073709551615.

Answer 5

Python 3 [166 bytes]

a,b=map(int,input().split());print(len(set([n if n%p==0 else 0 for p in [x for x in range(a,b) if sum(y for y in range(1,x) if x%y==0)==x] for n in range(a,b+1)]))-1)

More readable:

// STDIN => a, b
a, b = map(int, input().split())

// list of perfect numbers
perfect = [x for x in range(a, b) if sum(y for y in range(1, x) if x % y == 0) == x]

// length(number % [any perfect number] == 0) => STDOUT
print(len(set([n if n % p == 0 else 0 for p in perfect for n in range(a, b + 1)])) - 1)

Here the list of perfect numbers is calculated inline but may be set statically. The number range should be bound by the machine's word size.

_{While this algorithm is deadly slow and takes ages for working with big numbers, it is at least short :)}

Answer 6

Jelly, 10 bytes

rÆD=Æṣ$§TL

Try it online!

Requiring space separated STDIN input bumps the byte count up to 15 bytes

How it works

rÆD=Æṣ$§TL - Main link. Takes a on the left and b on the right
r          - Yield [a, a+1, ..., b-1, b]
 ÆD        - Generate the divisors of each
      $    - Over each list of divisors, d:
    Æṣ     -   Generate the proper divisor sum of each value in d
   =   §   -   Count how many are equal to their proper divisor sum
             This maps numbers with perfect to divisors to a non-zero value
             and those without to 0
        TL - Count the number of non-zero elements

Answer 7

Perl 5 -MList::Util=sum,any -pl, 77 bytes

$"=$_,$\+=any{$"%$_==0}grep{//;2*$_==sum grep{$'%$_==0}1..$_}2..$"for$_..<>}{

Try it online!

Ungolfed:

$_ = ; # implicit by -p command line switch
for$_($_..){ # loop over the range from $_ to the next input
   $"=$_;                           # store a copy of the current number ($_) so it can be used in sub-loops
   $\+=                             # counter for number of perfectly divisible numbers found
      any{$"%$_==0}                 # check if the current number ($") is evenly divisible by a:
         grep{//;2*$_==             # PERFECT NUMBER: a number where twice the number equals
            sum grep{$'%$_==0}1..$_ #                 the sum of the numbers which divide it evenly
         }2..$"                     # that exists in range of 2 to the current number
}
print$\; # implicit by -p command line switch

Answer 8

Vyxal, 11 bytes

ṡƛ'∆K=;Ḋa;∑

Try it Online!

9 bytes with s flag

12 bytes accounting for space seperated inputs

Explained

ṡƛ'∆K=;Ḋa;∑
ṡƛ       ;  # Over each item x in the range [input a, input b]
  '∆K=;     #   Keep items from the range [1, x] that are perfect numbers
       Ḋa   #   And is x divisible by any of those perfect numbers?
          ∑ # Sum the number of numbers that are divisible by a perfect number