p1, cs430 - 22

# Alexander Lucas

def factors(n)
  ((n < 0 ? n : 1)..n.abs).select { |x| x != 0 && n % x == 0 }
end

def primes(n)
  nums = n < 2 ? (return []; []) : (2..n).to_a
  nums.each do |x|
    nums.drop(nums.find_index(x) + 1).each do |y|
      nums.delete(y) if y % x == 0
    end
  end
end

def prime_factors(n)
  factors(n) & primes(n)
end

def perfects(n)
  prime_bound = Integer((Math.log((0.5)*Math.sqrt(8*n+1)+1))/(Math.log(2)))
  primes(prime_bound).map do |x| 2**(x-1)*(2**x-1) end
end

def pythagoreans(n)
  return [] if n < 1

  (a, b, c, d) = [0, 1, 1, n]
  ans = []
  while c <= n do
    k = (n + b) / d
    (a, b, c, d) = [c, d, k*c-a, k*d-b]
    ans << [a, b]
  end

  ans = ans
    .map do |x| x << Math.sqrt((x[0]*x[0]) + (x[1]*x[1])) end
    .select do |x| x[2] % 1 == 0 && x[2] <= n end
    .map do |x| x[0..1] << Integer(x[2]) end

  def aprims(triple, limit)
    2.upto(limit).map do |x|
      (a, b, c) = triple; [x*a, x*b, x*c]
    end .reject do |(_, _, c)|
      c > limit
    end
  end

  (0..ans.length - 1).each do |i|
    ads = aprims(ans[i], n)
    ads.each do |x|
      ans << x
    end
  end

  ans.sort
end
end