# Finding a formula for a sequence with recurring digits

1. Jul 26, 2012

### spiritzavior

how do i determine the formula for the sequence below?

1,1,2,2,2,2,3,3,3,3,3,4,4,4,4,4,4,4,4,...,n,n,n,n,n,...,n,...

need some instructions. thanks in advance

2. Jul 26, 2012

### Dickfore

Ok, there are subsequences of equal entries (increasing by one) in a row, and the numbers of equal entries in each of them form the following sequence:

2, 4, 5, 8, ...

I can't see any regularity. Sorry.

3. Jul 26, 2012

### haruspex

I can't see a pattern here: you have two 1s, four 2s, five 3s and eight 4s. Can you confirm that you've written it out correctly?

4. Jul 27, 2012

### ramsey2879

Seems like one too many 2's with n-1 repeated F(n+1) times for n = 2,3,4,5,... .

Last edited: Jul 27, 2012
5. Jul 28, 2012

### spiritzavior

sorry, i've typed it incorrectly, it should be:

1,1,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,4,4,...

two 1s, four 2s, six 3s, eight 4s,...

6. Jul 28, 2012

### haruspex

If you don't mind the use of [] (integer part of) it's [1/2 +√(n-3/4)]

7. Jul 28, 2012

### Dickfore

So, there are $2 n$ n's. The total number of elements no smaller than n is:
$$\sum_{k = 1}^{n}{2 k} = n(n + 1)$$

Thus, all the elements with an index k that satisfies:
$$(n - 1) n < k \le n (n + 1)$$
are equal to $x_k = n$ (why?). Can you find n, given k from the above inequalities?
$$n^2 + n - k \ge 0 \Rightarrow n \ge -\frac{1}{2} + \sqrt{k + \frac{1}{4}}$$
$$n^2 - n - k < 0 \Rightarrow n < \frac{1}{2} + \sqrt{k + \frac{1}{4}}$$

If you know the [STRIKE]floor[/STRIKE] floor function, which is the same as integer part for positive integers, you should be able to deduce:
$$x_k = \mathrm{Ceiling} \left[ \sqrt{k + \frac{1}{4}} - \frac{1}{2}\right]$$

Last edited: Jul 28, 2012
8. Jul 28, 2012

### acabus

$a(n) = round(\sqrt{n})$ seems to work, not that I could prove it.

This is where a(1) is the first entry in the sequence.

9. Jul 28, 2012

### Anti-Crackpot

Good intuition abacus...

A000194 n appears 2n times; also nearest integer to square root of n
http://oeis.org/A000194

If one desires that digits are repeated 2n - 1 times, that's an easy one: floor [sqrt n]

10. Jul 28, 2012

### Dickfore

The definition of ceiling and round functions is:
$$\mathrm{Ceiling}(x) \equiv n, \ n \le x < n + 1$$
$$\mathrm{Round}(x) \equiv m, \ \vert x - m \vert < 1/2$$
(the last definition is ambiguous if the argument is half-integer, but there can never happen for acabus's argument)

We want to know for what x, and y, $\mathrm{Ceiling}(x) \stackrel{?}{=} \mathrm{Round}(y) = n$. From the above definitions, this happens when:
$$n \le x < n + 1, \ n - 1/2 < y < n + 1/2$$
or, if we rewrite these inequalities for n, we get:
$$x - 1 < n \le x, \ y - 1/2 < n < y + 1/2$$
Then, a necessary and sufficient (why?) condition is:
$$x - 1 < y + 1/2, \ y - 1/2 < x$$

In our case, $x = \sqrt{k + 1/4} - 1/2$, and $y= \sqrt{k}$, so we have:
$$\sqrt{k + 1/4} - 1/2 - 1 < \sqrt{k} + 1/2 \Leftrightarrow \sqrt{k + 1/4} - \sqrt{k} < 2$$
$$\sqrt{k} - 1/2 < \sqrt{k + 1/4} - 1/2 \Leftrightarrow \sqrt{k + 1/4} - \sqrt{k} > 0$$
The second inequality is surely true, but the first is proven as follows:
$$\begin{array}{l} \sqrt{k + 1/4} - \sqrt{k} \stackrel{?}{<} 2 \\ 0 < \sqrt{k + 1/4} \stackrel{?}{<} \sqrt{k} + 2 \\ k + 1/4 \stackrel{?}{<} k + 4 \sqrt{k} + 4 \\ 0 \stackrel{\surd}{<} \sqrt{k} + 15/16 \end{array}$$
This is surely true. Therefore, both the formulas give the same output for all positive integers.

11. Jul 28, 2012