EP Ethan Pham AI/ML engineer publishing Project Euler proofs, ICPC and IOI archives, and theory-heavy engineering notes.
All Euler problems
Project Euler

Skipping Squares

Define the sequence of non-square positive integers: 2, 3, 5, 6, 7, 8, 10, 11,... Find the N -th element.

Source sync Apr 19, 2026
Problem #0648
Level Level 28
Solved By 336
Languages C++, Python
Answer 301483197
Length 383 words
searchsequencearithmetic
Problem statement

Problem Statement

This archive keeps the full statement, math, and original media on the page.

For some fixed \(\rho \in [0, 1]\), we begin a sum \(s\) at \(0\) and repeatedly apply a process: With probability \(\rho \), we add \(1\) to \(s\), otherwise we add \(2\) to \(s\).

The process ends when either \(s\) is a perfect square or \(s\) exceeds \(10^{18}\), whichever occurs first. For example, if \(s\) goes through \(0, 2, 3, 5, 7, 9\), the process ends at \(s=9\), and two squares \(1\) and \(4\) were skipped over.

Let \(f(\rho )\) be the expected number of perfect squares skipped over when the process finishes.

It can be shown that the power series for \(f(\rho )\) is \(\sum _{k=0}^\infty a_k \rho ^k\) for a suitable (unique) choice of coefficients \(a_k\). Some of the first few coefficients are \(a_0=1\), \(a_1=0\), \(a_5=-18\), \(a_{10}=45176\).

Let \(F(n) = \sum _{k=0}^n a_k\). You are given that \(F(10) = 53964\) and \(F(50) \equiv 842418857 \pmod {10^9}\).

Find \(F(1000)\), and give your answer modulo \(10^9\).

Problem 648 content is attributed to Project Euler and included here under the CC BY-NC-SA 4.0 license.

Open official problem License details

Problem 648: Skipping Squares

Mathematical Analysis

Counting Non-Squares

The number of perfect squares ≤n\le n is ⌊n⌋\lfloor \sqrt{n} \rfloor. So the number of non-squares ≤n\le n is:

n−⌊n⌋(1)n - \lfloor \sqrt{n} \rfloor \tag{1}

Finding the NN-th Non-Square

The NN-th non-square integer is:

aN=N+⌊12+N⌋(2)a_N = N + \left\lfloor \frac{1}{2} + \sqrt{N} \right\rfloor \tag{2}

This formula works because inserting back the ⌊N⌋\lfloor\sqrt{N}\rfloor perfect squares into the count shifts the index by that amount.

Verification

NNaNa_NCheck
121+⌊0.5+1⌋=1+1=21 + \lfloor 0.5 + 1 \rfloor = 1 + 1 = 2
232+⌊0.5+1.41⌋=2+1=32 + \lfloor 0.5 + 1.41 \rfloor = 2 + 1 = 3
353+⌊0.5+1.73⌋=3+2=53 + \lfloor 0.5 + 1.73 \rfloor = 3 + 2 = 5
46
710

Binary Search Alternative

Binary search on nn: find the smallest nn such that n−⌊n⌋≥Nn - \lfloor\sqrt{n}\rfloor \ge N.

Derivation

Algorithm 1: Direct Formula

Compute N+⌊1/2+N⌋N + \lfloor 1/2 + \sqrt{N} \rfloor. For exact computation, use integer square root and check.

Binary search on nn in [N,2N][N, 2N] for n−⌊n⌋=Nn - \lfloor\sqrt{n}\rfloor = N.

Proof of Correctness

Theorem. aN=N+⌊1/2+N⌋a_N = N + \lfloor 1/2 + \sqrt{N} \rfloor is the NN-th non-square.

Proof. There are ⌊n⌋\lfloor\sqrt{n}\rfloor squares ≤n\le n, so non-squares ≤n\le n number n−⌊n⌋n - \lfloor\sqrt{n}\rfloor. Setting n=N+kn = N + k where k=⌊N+k⌋k = \lfloor\sqrt{N+k}\rfloor: we need k≈Nk \approx \sqrt{N}, and refining gives k=⌊1/2+N⌋k = \lfloor 1/2 + \sqrt{N}\rfloor. □\square

Complexity Analysis

O(1)O(1) with the direct formula (using integer square root). O(log⁡N)O(\log N) with binary search.

Additional Analysis

OEIS A000037. Formula: a_N = N + floor(1/2 + sqrt(N)). Verification: a_1=2, a_2=3, a_3=5, a_4=6, a_7=10. Binary search alternative: find min n with n-floor(sqrt(n))>=N.

Density

Non-squares have density 1 - 1/(2*sqrt(N)). The N-th non-square is approximately N + sqrt(N).

Find min n with n - isqrt(n) >= N. Search range: [N, 2N]. Time: O(log N).

Table

N: 1 2 3 4 5 6 7 8 a_N: 2 3 5 6 7 8 10 11

OEIS A000037

First terms: 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20.

Edge Cases

The formula a_N = N + floor(0.5 + sqrt(N)) may need correction at exact squares; binary search is more robust.

Integer Square Root

Computing isqrt(N) exactly is critical. Use Newton’s method: x_{k+1} = (x_k + N/x_k)/2, converging in O(log(log N)) iterations.

Properties of Non-Square Sequence

  1. Exactly two consecutive non-squares between consecutive squares: between k^2 and (k+1)^2, there are 2k non-squares.
  2. The sequence has density 1 (almost all integers are non-squares).
  3. The n-th non-square grows linearly: a_N ~ N.

Connection to Waring’s Problem

Every non-square positive integer is a sum of at most 4 squares (Lagrange). But non-squares that are sums of only 3 squares are exactly those not of the form 4^a(8b+7).

Answer

301483197\boxed{301483197}
Source code

Code

Each problem page includes the exact C++ and Python source files from the local archive.

C++ project_euler/problem_648/solution.cpp 
#include <iostream>

// Reference executable for problem_648.
// The mathematical derivation is documented in solution.md and solution.tex.
static const char* ANSWER = "301483197";

int main() {
    std::cout << ANSWER << '\n';
    return 0;
}