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

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
• 18 is not a perfect number! I guess you meant 28? (Since 18!=9+6+3+2+1, while 28=14+7+4+2+1). Jan 17, 2014 at 9:17
• @Vereos the question says Count how many numbers are divisible by perfect numbers  Jan 17, 2014 at 9:27
• Woah, I've been misleaded by the question's name. Thank you! Jan 17, 2014 at 9:29
• @Peter Taylor Arbitrary integers
– Wasi
Jan 17, 2014 at 9:37
• Well technically 1 is perfect... Jan 17, 2014 at 14:22

## 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 # 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. # 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. # 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. • In C global ints are initialized to 0 by default so you don't need to set c=0 :) – Josh Jan 19, 2014 at 0:52 • To save 1 char you could move one of your ints into the main declaration, ex main(i) (saves a comma character). – Josh Jan 19, 2014 at 0:53 • Oh, you're right! I also removed a couple of useless {}. Jan 19, 2014 at 1:08 • You can remove the pair of braces around your if statement by changing the contents to be c++,i=4; – Josh Jan 19, 2014 at 1:49 • Yes, I did it. Well, not in the prettified version, but that's not supposed to be short, isn't it? Jan 19, 2014 at 2:24 ## 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 :) # 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


# 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