sidef-scripts/Math/partial_sums_of_powerfree_part.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 20 August 2021
# https://github.com/trizen

# Sub-linear formula for computing the partial sum of the k-powerfree part of numbers <= n.

# See also:
#   https://oeis.org/A007913 -- Squarefree part of n: a(n) is the smallest positive number m such that n/m is a square.
#   https://oeis.org/A050985 -- Cubefree part of n.
#   https://oeis.org/A069891 -- a(n) = Sum_{k=1..n} A007913(k), the squarefree part of k.

func f(n, r) {
    n.factor_prod {|p|
        1 - p**r
    }
}

func powerfree_part_sum(n, r=2) {
    sum(1..n.iroot(r), {|k|
        f(k, r) * faulhaber(idiv(n, k**r), 1)
    })
}

for k in (2..10) {
    printf("Sum of %2d-powerfree part of numbers <= 10^j: {%s}\n", k, 7.of {|j| powerfree_part_sum(10**j, k) }.join(', '))
}

__END__
Sum of  2-powerfree part of numbers <= 10^j: {1, 38, 3233, 328322, 32926441, 3289873890, 328984021545, 32898872196712, 3289866649713946, 328986818422458525}
Sum of  3-powerfree part of numbers <= 10^j: {1, 48, 4341, 423422, 42307792, 4231510721, 423168867323, 42316819978538, 4231674929522571, 423167595545369699}
Sum of  4-powerfree part of numbers <= 10^j: {1, 55, 4655, 464251, 46382816, 4638539465, 463852501943, 46385283123175, 4638527873315616, 463852816114474745}
Sum of  5-powerfree part of numbers <= 10^j: {1, 55, 4864, 482704, 48270333, 4826777870, 482672975112, 48267321925901, 4826732665235263, 482673247658594364}
Sum of  6-powerfree part of numbers <= 10^j: {1, 55, 4987, 492212, 49167065, 4916054515, 491597851229, 49159726433201, 4915972406234581, 491597239622128025}
Sum of  7-powerfree part of numbers <= 10^j: {1, 55, 5050, 496944, 49591853, 4958924582, 495890504497, 49589026540242, 4958902946849591, 495890297494178938}
Sum of  8-powerfree part of numbers <= 10^j: {1, 55, 5050, 498970, 49799540, 4979820070, 497977273243, 49797721800745, 4979772120992951, 497977210585462720}
Sum of  9-powerfree part of numbers <= 10^j: {1, 55, 5050, 499989, 49907910, 4989989560, 499000372993, 49899962707231, 4989997192210079, 498999721730951028}
Sum of 10-powerfree part of numbers <= 10^j: {1, 55, 5050, 500500, 49958965, 4995128633, 499504727624, 49950367771436, 4995036826408388, 499503683030989912}