Sum of the First n Non-Square Integers

[@jacemandt]

I like the choice of problem here! Usually videos are made about problems that have surprisingly simple final answers. This one doesn't, but instead it demonstrates how to approach the problem from scratch and how to exploit properties of integers vs. real numbers to simplify. A good process-centered problem, rather than a results-centered problem.

[@jaafars.mahdawi6911]

You just spoke my mind here. Except i'd add that almost all of this channel's content is about such brilliant choices. Thanks Dr. Barker for giving us another Axiom of KZbin Choice.

[@admiralbananas]

This ended up being a lot more difficult of a problem than i thought it'd be and your opening example of n=1000 did a good job of illustrating that. Great job making this video accessible as always, Dr Barker. Keep up the great work.

[@yasinmohammadi8]

great video

[@ktuluflux]

If I want to learn to approach something like this from scratch, are there any go-to/standard books for beginner number theory? Seems like a fun way to spend weeknights after work.

[@DrBarker]

I'm not sure if it's the sort of level you're looking for, but perhaps you could check out the beginning of the number theory chapter in Gelca's "Putnam and Beyond". This has lots of interesting problems, but doesn't require specific knowledge of more advanced results from number theory.

[@wesleydeng71]

Interesting! I have a further question. Can we find f(n)= # of all powers no larger than n? e.g. f(10) = 4. f(100) = 13, etc.

[@rogerkearns8094]

I make f(100) = 13. 1 4 8 9 16 25 27 32 36 49 64 81 100.

[@aweebthatlovesmath4220]

Using that if n is a perfect a-power and b divides a then n is a perfect b-power and n is a perfect a and b power then n is a perfect [a,b] (lcm) power by inclusion and exclusion theorem on number of pefect p-powers which is same but instead of square root we have p-th root we get your function (where p runs through every prime less then n)

[@fullfungo]

I believe, it is probably f(n) = - Σ_k>1 [μ(k)*floor(n^1/k)] The idea is quite simple. The amount of p-powers upto n is floor(n^1/p). So we just have to sum up all these amounts to get all squares + all cubes +… Notice that all 4th powers are already among all 2nd powers. And generally all p^m-th powers are already contained among all p-th powers. However, if we just count all 2nd and 3rd powers together, we would count all 6-th powers twice, so we have to subtract it. And in general all p*q-th powers are counted twice. Similarly, all p*q*r-th powers are not counted if we subtract all previously mentioned overlaps. For example, if we add 2-nd, 3-rd and 5-th powers, we have to remove 6-th, 10-th and 15-th powers; since we counted them twice. Then all 30-th powers were added 3 times from 2,3,5 and removed 3 times from 6,10,15. Therefore, we still have to add them. And in general, we have to add all powers that have odd amount of prime factors, subtract all that have an even number of prime factors, and ignore all that have repeating primes in their prime factorisation, therefore we just multiply by -μ(k), the negative of the Möbius function.

[@Jack_Callcott_AU]

I have wondered about this, so this is an interesting video that gives a useful result, but what about a formula for the sum of the first n square-free integers. I bet that wouldn't be easy to derive.

[@rob876]

floor(√n + ½) is the same as round(√n)

[@DrBarker]

Good point - so we only need to deal with the extra square number (like 1024 for n = 1000) when √n rounds up, rather than down. I now wonder if there is an intuitive way to understand this, and perhaps it could save doing some algebra as in the video.

[@yurenchu]

The sum of the first k non-square (positive) integers is W(k) = k(k+1)/2 + k*r + (r - r³)/3 where r = round(√k) So for the sum of the first 1000 non-square positive integers, we have k = 1000 , r = 32 , and W(1000) = 1000(1000+1)/2 + 1000*32 + (32 - 32³)/3 = = 500(1001) + 1000*32 + 32(1 - 1024)/3 = 521588

[@yurenchu]

Derivation of formula for W(k) : Let n be the k'th non-square (positive) integer. Then k = n - floor(√n) ... [eq. 1] Let m = floor(√n) , then (since n is non-square) m² < n < (m+1)² . ... Subtract m from each side ... m² - m < n - m < (m+1)² - m ... Note that (n-m) is an integer, and so are LHS and RHS, with "strictly less than" signs between them ... m² - m + ¼ < (n - m) < (m+1)² - (m+1) + ¼ ... from eq. 1 , k = (n - m) ... (m-½)² < k < (m+1- ½)² (m-½) < √k < (m+½) ⇒ round(√k) = m So we can rewrite eq. 1 as k = n - floor(√n) = (n - m) = n - round(√k) ⇒ n = k + round(√k) W(k) = { ∑ (j'th non-square integer) , from j=1 to j=k } = = { ∑ j , from j=1 to j=n } - { ∑ j² , from j=1 to j=floor(√n) } = { ∑ j , from j=1 to j=n } - { ∑ j² , from j=1 to j=round(√k) } ... introduce r = round(√k) ... = { ∑ j , from j=1 to j=n } - { ∑ j² , from j=1 to j=r } = n(n+1)/2 - r(r+0.5)(r+1)/3 ... substitute n = k+r ... = (k+r)(k+r+1)/2 - r(r+0.5)(r+1)/3 = (k² + 2kr + r² + k + r)/2 - (2r³ + 3r² + r)/6 = (3k² + 6kr + 3r² + 3k + 3r)/6 - (2r³ + 3r² + r)/6 = (3k² + 6kr + 3r² + 3k + 3r - 2r³ - 3r² - r)/6 = (3k² + 3k + 6kr + 2r - 2r³)/6 = (k² + k)/2 + kr + (r - r³)/3 = k(k+1)/2 + kr + r(1-r²)/3

[@kallekula84]

I solved it programmatically in OCaml to be 521, 588

[@wyboo2019]

i got f(n) in a different way. the number of square numbers