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). – Vereos Jan 17 '14 at 9:17
• @Vereos the question says Count how many numbers are divisible by perfect numbers – ace_HongKongIndependence Jan 17 '14 at 9:27
• Woah, I've been misleaded by the question's name. Thank you! – Vereos Jan 17 '14 at 9:29
• @Peter Taylor Arbitrary integers – Wasi Jan 17 '14 at 9:37
• Then I suggest you edit the question to make that explicit before people start submitting answers with 32-bit ints. – Peter Taylor Jan 17 '14 at 9:41

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={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={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={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 '14 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 '14 at 0:53 • Oh, you're right! I also removed a couple of useless {}. – izabera Jan 19 '14 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 '14 at 1:49 • Yes, I did it. Well, not in the prettified version, but that's not supposed to be short, isn't it? – izabera Jan 19 '14 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 :) PHP, 248 I guess there could be way shorter solutions, but here's mine. I used the STDIN constant to achieve the stdin spec, but I used echo to output. fscanf(STDIN,"%d\n",$a);fscanf(STDIN,"%d\n",$b);$l=array(6,28,496,8128,33550336,8589869056,137438691328,2305843008139952128);$x=array();foreach($l as&$k){if($k>=$a){$c=$k;while($c<=$b){if($c%$k==0&&!in_array($c,$x)){$r++;$x[]=$c;}$c+=$k;}}}echo $r; Readable: fscanf(STDIN,"%d\n",$a);
fscanf(STDIN,"%d\n",$b);$l=array(6,28,496,8128,33550336,8589869056,137438691328,2305843008139952128);
$x=array(); foreach($l as&$k){ if ($k>=$a){$c=$k; while($c<=$b){ if($c%$k==0&&!in_array($c,$x)){$r++;
$x[]=$c;
}
$c+=$k;
}
}
}
echo \$r;
• The spec requires you to support big integers, so in PHP you probably want bc_math (and in any language you can't hard-code the list of perfect numbers). – Peter Taylor Jan 17 '14 at 11:15