sum of pow k

pow_k_sum.rb

require 'matrix'
def powsum_params(k)
  Matrix[*(k+2).times.map{|a|
    (k+2).times.map{|b|(a+1)**b}
  }].lup.solve((k+2).times.map{|n|(1..n+1).sum{_1**k}}).to_a
end

def assign_params(params, x)
  params.each_with_index.sum {|p,i|p*x**i}
end


def params_divmod(params, denom)
  params = params.dup
  denom = denom.dup
  params.pop while params[-1] == 0
  denom.pop while denom[-1] == 0
  raise unless params[-1] != 0 && denom[-1] != 0
  ans = (params.size - denom.size + 1).times.reverse_each.map do |shift|
    v = params[denom.size - 1 + shift].quo(denom[-1])
    denom.size.times do |i|
      params[i + shift] -= v * denom[i]
    end
    v
  end.reverse
  params.pop while params[-1] == 0
  [ans, params]
end
def inspect_params(params)
  params.each_with_index.map do |p, k|
    p = p.to_i if p.to_i == p
    next if p == 0
    l = p==1 && k!=0 ? '' : p.to_s
    r = k==0 ? '' : k==1 ? 'n' : "n^#{k}"
    if r.empty?
      l
    elsif l.include? ('/')
      l[0] == '-' ? "-(#{l[1..]})#{r}" : "(#{l})#{r}"
    else
      "#{l}#{r}"
    end
  end.compact.reverse.join(' + ').gsub(' + -', ' - ')
end

(0..10).map do |k|
  params = powsum_params(k)
  ans=[];(1..20).each{|a|(-40..40).each{|b|ans<<b.quo(a) if assign_params(params, b.quo(a))==0}};ans.sort.uniq
  hoge = []
  ans.reverse_each do |a|
    while true
      div, mod = params_divmod(params, [-a, 1])
      break unless mod.empty?
      hoge << [-a, 1]
      params = div
    end
  end
  hoge << params
  puts "k=#{k}"
  puts hoge.map{inspect_params(_1)}.map { |s| s.match?(/ [+-] /) ? "(#{s})" : s }.join(' * ')
  puts
end

pow_k_sum.txt

k=0
n * 1

k=1
n * (n + 1) * 1/2

k=2
n * (n + 1/2) * (n + 1) * 1/3

k=3
n * n * (n + 1) * (n + 1) * 1/4

k=4
n * (n + 1/2) * (n + 1) * ((1/5)n^2 + (1/5)n - 1/15)

k=5
n * n * (n + 1) * (n + 1) * ((1/6)n^2 + (1/6)n - 1/12)

k=6
n * (n + 1/2) * (n + 1) * ((1/7)n^4 + (2/7)n^3 - (1/7)n + 1/21)

k=7
n * n * (n + 1) * (n + 1) * ((1/8)n^4 + (1/4)n^3 - (1/24)n^2 - (1/6)n + 1/12)

k=8
n * (n + 1/2) * (n + 1) * ((1/9)n^6 + (1/3)n^5 + (1/9)n^4 - (1/3)n^3 - (1/45)n^2 + (1/5)n - 1/15)

k=9
n * n * (n + 1) * (n + 1) * ((1/10)n^6 + (3/10)n^5 + (1/20)n^4 - (2/5)n^3 + (1/20)n^2 + (3/10)n - 3/20)

k=10
n * (n + 1/2) * (n + 1) * ((1/11)n^8 + (4/11)n^7 + (8/33)n^6 - (6/11)n^5 - (10/33)n^4 + (8/11)n^3 + (2/33)n^2 - (5/11)n + 5/33)