# My Favorite Sequences: A261865

This is the first installment in a new series, “My Favorite Sequences”. In this series, I will write about sequences from the On-Line Encyclopedia of Integer Sequences that I’ve authored or spent a lot of time thinking about.

I’ve been contributing to the On-Line Encyclopedia of Integer Sequences since I was an undergraduate. In December 2013, I submitted sequence A233421 based on problem A2 from the 2013 Putnam Exam—which is itself based on “Ron Graham’s Sequence” (A006255)—a surprising bijection from the natural numbers to the non-primes. As of today, I’ve authored over 475 sequences based on puzzles that I’ve heard about and problems that I’ve dreamed up.

## A261865: Multiples of square roots

(This problem is closely related to Problem 13 in my Open Problems Collection.)

In September 2015, I submitted sequence A261865:

$$A261865(n)$$ is the least integer $$k$$ such that some multiple of $$\sqrt k$$ falls in the interval $$(n, n+1)$$.

For example, $$A261865(3) = 3$$ because there is no multiple of $$\sqrt 1$$ in $$(3,4)$$ (since $$3 \sqrt{1} \leq 3$$ and $$4 \sqrt{1} \geq 4$$); there is no multiple of $$\sqrt{2}$$ in $$(3,4)$$ (since $$2 \sqrt{2} \leq 3$$ and $$3 \sqrt 2 \geq 4$$); but there is a multiple of $$\sqrt 3$$ in $$(3,4)$$, namely $$2\sqrt 3$$.

As indicated in the picture, the sequence begins $$\color{blue}{ 2,2,3,2,2},\color{red}{3},\color{blue}{2,2,2},\color{red}{3},\color{blue}{2,2},\color{red}{3},\color{blue}{2,2,2},\color{red}{3},\color{blue}{2,2},\color{red}{3},\color{blue}{2,2},\color{magenta}{7},\dots.$$

As the example illustrates, $$1$$ does not appear in the sequence. And almost by definition, asymptotically $$1/\sqrt 2$$ of the values are $$2$$s.

Let’s denote the asymptotic density of terms that are equal to $$n$$ by $$d_n$$. It’s easy to check that $$d_1 = 0$$, (because multiples of $$\sqrt 1$$ are never between any integers) and $$d_2 = 1/\sqrt 2$$, because multiples of $$\sqrt 2$$ are always inserted. I conjecture in Problem 13 of my Open Problem Collection that $$a_n = \begin{cases}\displaystyle\frac{1}{\sqrt n}\left(1 – \sum_{i=1}^{n-1} a_i\right) & n \text{ is squarefree}\\[5mm] 0 & \text{otherwise}\end{cases}$$

If this conjecture is true, then the following table gives approximate densities.

This was computed with the Mathematica code:

d[i_] := (d[i] = If[
SquareFreeQ[i],
N[(1 - Sum[d[j], {j, 2, i - 1}])/Sqrt[i], 50],
0
])


## Finding Large Values

I’m interested in values of $$n$$ such that $$A261865(n)$$ is large, and I reckon that there are clever ways to construct these, perhaps by looking at some Diophantine approximations of $$\sqrt{2}, \sqrt{3}, \sqrt{5}, \sqrt{6}, \dots$$. In February, I posted a challenge on Code Golf Stack Exchange to have folks compete in writing programs that can quickly find large values of $$A261865(n)$$.

Impressively, Noodle9’s C++ program won the challenge. In under a minute, this program found that the input $$n=1001313673399$$ makes $$A261865$$ particularly large: $$A261865(1001313673399) = 399$$. Within the time limit, no other programs could find a value of $$n$$ that makes $$A261865(n)$$ larger.

## Related Ideas

Sequence $$A327953(n)$$ counts the number of positive integers $$k$$ such that there is some integer $$\alpha^{(n)}_k > 2$$ where $$\alpha^{(n)}_k\sqrt{k} \in (n, n+1)$$. It appears to grow roughly linearly like $$A327953(n) \sim 1.3n$$, but I don’t know how to prove this.

• Take any function $$f\colon\mathbb N \rightarrow \mathbb R$$ that is positive, has positive first derivative, and has negative second derivative. Then, what is the least $$k$$ such that some multiple of $$f(k)$$ is in $$(n,n+1)$$?
• For example, what is the least integer $$k \geq 3$$ such that there is a multiple of $$\ln(k)$$ in $$(n, n+1)$$?
• What is the least $$k \in \mathbb N$$ such that there exists $$m \in \mathbb N$$ with $$k2^{1/m} \in (n,n+1)$$?
• What is the least $$m \in \mathbb N$$ such that there exists $$k \in \mathbb N$$ with $$k2^{1/m} \in (n,n+1)$$?
• A343205 is the auxiliary sequence that gives the value $$m$$ such that $$m\sqrt{A261865(n)} \in (n, n+1)$$. Does this sequence have an infinite limit inferior?