Euler Projesi 221. Soru

Aleksandria Tamsayıları

$$A=pqr \textrm{ ve} 1/A=1/p+1/q+1/r$$
eşitliklerini sağlayan $p,q,r$ tamsayılarının bulunması durumunda $A$ sayısına bir "Aleksandria tamsayısı" denir. Örneğin, 630 bir Aleksandria tamsayısıdır ($p=5, q=-7, r=-18$).
Aslında 630, 6. Aleksandria tamsayısı, ilk 6 Aleksandria tamsayısı ise 6, 42, 120, 156, 420 ve 630'dur.

O halde 150000. Aleksandria tamsayısı kaçtır?

Cevap: 1884161251122450

Mathematica:

m = 10^16;
maxb = Floor[m^(1/3)];

res = Union[Reap[For[b = 1, b <= maxb, b++;
      a = b^2 + 1;
      d = Divisors[a];
      end = Ceiling[Length[d]/2];
      For[i = 1, i <= end, i++,
       v = b (b + d[[i]]) (b + a/d[[i]]);
       If[v <= m, Sow[v]]]]][[2, 1]]];

If[Length[res] >= 149999, res[[149999]]]

Python:

from heapq import heappushpop
from itertools import count

def main():
    target = 150000
    found = [-10000000000000000] * target
    for p in count():
        if p % 1000 == 0:
            print -found[0]
        for q in xrange(-p * 2, -p):
            n = p * q
            if n * (1 - n) % (p + q) == 0:
                a = n * (1 - n) // (p + q)
                if a % n == 0:
                    heappushpop(found, -a)

main()

Haskell:

merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys)
      | snd x < snd y  = x:merge xs (y:ys)
      | otherwise      =y:merge (x:xs) ys

mergels [] = []
mergels (a:b:[]) = merge a b
mergels (a:b:c:rest) = ab ++ mergels (toobig:c:rest)
    where
        (p,r)=head c
        cutoff = (4*p+2)*p*p
        ab' = merge a b
        ab = takeWhile (\x->(snd x)<cutoff) ab'
        toobig = dropWhile (\x->(snd x)<cutoff) ab'

subAlex a = [(a,a*(a+db)*(a+(div as db)))| 
             db<-[a,a-1..1],mod as db == 0]
    where as = a*a+1

alex = mergels [subAlex a|a<-[1..]]

main = print $ alex !! (150000-1)

Java:

with(numtheory):with(ListTools):gen:=proc(k)
> local t,n,i,L;
> L:=NULL;
> t:=divisors(k^2+1); n:=nops(t);
> for i from 1 to n/2 do
>   L:=L,k*(k-t[i])*(t[n-i+1]-k) od;
> [L];
> end:
> sort(MakeUnique([seq(gen(k)[],k=1..300000)]))[150001];

                           1884161251122450

Ruby:

#Problem 221 from projectreuler.net
#
start_time=Time.now
input=ARGV[0].to_i
input2=ARGV[1].to_i
GOAL=input

def factor(n)
 limit=Math.sqrt(n).to_i
 (1..limit).select {|x| n%x==0}
end

def ai(p,k)
 p**4/k + 2*p**3 + k*p**2 +p**2/k +p
end

count,p=1,1
alex=[[6,1,2,3]]

while count<GOAL
 p+=1
 n=p**2+1
 k=factor(n)
 k.each do |x|
  q=p+x
  r=(1+p*q)/(q-p)
  alex.push([p*q*r,p,q,r])
  count += 1
 end
 printf"found #{count} at #{Time.now-start_time}\n" if count%100==0
end

alex.sort!
printf"The #{count}th Alexandrian number is #{alex.last.inspect}\n"
printf"The #{input2}th Alexandrian number is #{alex[input2-1].inspect}\n"

puts "\n"
printf"Time to run= #{Time.now-start_time}\n"

Basic:

Sub prob_221()
br = 1
col = 1
For p = 2 To 500000
 For i = 1 To p - 1
  ch = (p * p + 1) / i
  If ch = Int(ch) Then
   br = br + 1
   Cells(br, col).Value = p * (p + i) * (p + ch)'q=p + i:r=p + ch
  If br = 60000 Then col = col + 1: br = 0
  End If
 Next i
Next p
End Sub