9
\$\begingroup\$
4, 32, 317, 3163, 31623, 316228, 3162278, 31622777, 316227767, 3162277661, 31622776602, 316227766017, 3162277660169, 31622776601684, 316227766016838, 3162277660168380, 31622776601683794, 316227766016837934, 3162277660168379332, 31622776601683793320, 316227766016837933200, 3162277660168379331999, 31622776601683793319989, 316227766016837933199890, ...

Or in other words: given n output the (n * 2)-th term of OEIS A017936: smallest number whose square has n digits.

Essentially we removed powers of 10 from mentioned OEIS serie.

Notes

As noted by Neil, there is a correlation with the digits of √(1/10), or even 10, 1 or any power of 10.
He also explained: the length of integers increases at each power of 10. The length of squares of integers increases at (the ceiling of) each power of √10. Half of these powers are also powers of 10, while the other half are powers of 10 multiplied by √(1/10).

Additionally a proof was given by jjagmath.
If n is the number where the square change from having k digits to \$k+1\$ digits then \$(n-1)^2<10^k\le n^2\$. So \$n-1 < 10^{k/2}\le n\$.
If k is even we have \$n = 10^{k/2}\$.
If \$k = 2m+1\$ then \$n-1 < 10^{m+1}\sqrt{1/10}< n\$ which explains why the first digits of n coincide with \$\sqrt{1/10}\$.

More notes

  • There is a difference between the last digit and the corresponding digit in \$\sqrt{1/10}\$, e.g. for the 5th term:
5th term     31623 
√(1/10)    0.31622776601..
                 ↑
  • Formal formula from OEIS A017936: a(n) = ceiling(10^((n-1)/2)) which includes powers of 10 terms.

  • The next term of x is between \$(x-1) * 10\$ and \$x * 10\$

Rules

This is , all usual golfing rules apply.

This is also so you can output:

  • n-th element
  • first n terms
  • infinite sequence

Floating point issues are allowed.
However answers that doesn't fail due to floating point issues are encouraged, you can post both solutions so that we'll see the difference, in that case please post best score as main solution and the other as alternative indicating both scores.

I could fork the challenge in two separate questions but.. I think duplicating is annoying and doesn't make much sense.
At the same time, considering what @Bubbler stated in the FP issues consensus: "Allowing or disallowing such functions (and intermediate floating point values) has a huge consequence, to the point that I could say it defines the actual challenge", I think it may be interesting to have a kind of challenge inside the challenge between FP issues in the same language.


Sandbox

\$\endgroup\$
0

11 Answers 11

5
\$\begingroup\$

Python, 26 bytes

lambda n:int(10**(n-.5))+1

Attempt This Online!

Has floating-point issues.

Python, 45 bytes

f=lambda n,i=1:10*100**n>i*i and f(n,i+1)or i

Attempt This Online!

Suboptimal - this is kind of an intermediary solution that shows another way of proving the formula. (I came up with this before seeing the formula, and once I saw the formula I noticed the connection)

Here is something of a derivation:

  1. Convert the loop-based solution (see below) to a recursive version:

    f=lambda n,i=1:n*2>len(str(i*i))and f(n,i+1)or i
    
  2. Replace len(str()) with a logarithmic computation \$ \lfloor\log(i^2) + 1 \rfloor \$:

    f=lambda n,i=1:n*2>floor(log10(i*i)+1)and f(n,i+1)or i
    
  3. It's an integer comparison, so the floor can be removed:

    f=lambda n,i=1:n*2>log10(i*i)+1and f(n,i+1)or i
    
  4. Raise both sides of the comparison as a power of 10:

    f=lambda n,i=1:10**(n*2)>10**(log10(i*i)+1)and f(n,i+1)or i
    
  5. Simplify:

    f=lambda n,i=1:100**n>i*i*10and f(n,i+1)or i
    
  6. Due to an off-by-one error, the answer I arrived at had 10* on the wrong side of the comparison; this is negated by choosing to use zero-indexed input (which is what I did instead of fixing the off-by-one error, because I'm lazy)

    At this point we have my intermdiate answer:

    f=lambda n,i=1:10*100**n>i*i and f(n,i+1)or i
    
  7. Square root both sides of the comparison:

    f=lambda n,i=1:sqrt(10)*10**n>i and f(n,i+1)or i
    
  8. Noting that the recursive wrapper now just searches for the first integral satisfying value of i, so it's pointless and can be replaced by floor +1:

    lambda n:floor(sqrt(10)*10**n)+1
    
  9. Some Python-specific tweaks to get a more optimal final answer:

    lambda n:int(10**(n-.5))+1
    

    This is now just the 26-byter above!

I'm tired, so there are probably a bunch of mistakes in this derivation, but they mirror my tired and mistake-ridden thought process!

Python 2, 41 bytes

n=i=input()
while`i*i`[-n:n]:i+=1
print i

Attempt This Online!

Completely non-formulaic solution.

-4 bytes with a cool slicing trick thanks to loopy walt.

-4 thanks to dingledooper

\$\endgroup\$
2
4
\$\begingroup\$

R, 19 bytes

\(n)10^(n-.5)%/%1+1

Attempt This Online!

Uses slight modification of the supplied formula.

\$\endgroup\$
4
\$\begingroup\$

Jelly, 7 bytes

Ḥ’⁵*ƽ‘

Try It Online!

Ḥ’⁵*ƽ‘  Main Link
Ḥ        Double
 ’       Decrement
  ⁵*     10 ^ that (smallest number with 2n digits)
    ƽ   Floor square root
      ‘  Increment

Square root + ceiling is one byte shorter but has floating point issues at n = 17 so Jonathan Allan provided a fix for +1 byte that avoids this issue.

\$\endgroup\$
2
  • \$\begingroup\$ ...and for no floating-point errors (which creep in at n=17 I believe) 7 bytes - Ḥ’⁵*ƽ‘ (since root ten is irrational we never increment when we shouldn't). \$\endgroup\$ Mar 25 at 11:50
  • \$\begingroup\$ @JonathanAllan ah, I was worried that'd be an issue. thanks \$\endgroup\$
    – hyper-neutrino
    Mar 25 at 18:41
3
\$\begingroup\$

Python 2, 42 bytes

It outputs the sequence infinitely. Notably, this approach goes for efficiency without losing precision as a result of floating-point math.

n=3
s=50
while 1:print-~n;n=n*5+s/n;s*=100

Try it online!

Explanation

The sequence can be computed by taking the first \$ n \$ digits of \$ \sqrt{10} \$, rounded up. To do this efficiently, we can use the Babylonian method. By taking an arbitrary number \$ x \$, and repeatedly applying it to the recurrence \$ x = \frac{1}{2}(x + \frac{10}{x}) \$, we can obtain an approximation of \$ \sqrt{10} \$ that converges extremely quickly (with quadratic convergence).

The above formula can be translated in Python as n=n/2+5/n. This works fine to simply compute the square root, but to compute the sequence we must scale \$ n \$ by a factor of 10 after each iteration. This can be done by having another variable s as the "scale factor", and modifying our original formula to scale by s. We end up with the following formula:

n=((n/s)/2+5/(n/s))*s*10; s*=10

It looks disgusting at first, but we can clean it up a bit:

n=((n/s)/2+5/(n/s))*s*10;s*=10  ->
n=(n/s/2+5*s/n)*s*10;s*=10      ->
n=n/s/2*s*10+5*s/n*s*10;s*=10   ->
n=n*5+5*s/n*s*10;s*=10          ->
n=n*5+50*s*s/n;s*=10            ->
n=n*5+s/n;s*=100                (starting with s=50)

The only thing left to do now is to modify the formula to round up. This turns out to be pretty simple, only changing n to n+1. I've checked that the first 500 terms of the sequence exactly match the output, though in theory, it is still susceptible to rounding errors.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 8 bytes

I⌈×₂χXχN

Try it online! Link is to verbose version of code. 0-indexed. Uses floating-point arithmetic. Explanation:

    χ       Predefined variable `10`
   ₂        Square root
  ×         Multiplied by
      χ     Predefined variable `10`
     X      Raised to power
       N    Input as a number
 ⌈          Ceiling
I           Cast to string
            Implicitly print

26 bytes using only integer arithmetic:

≔⁰ηFN«≧×χηW﹪L×⊕η⊕η²≦⊕η»I⊕η

Try it online! Link is to verbose version of code. 1-indexed. Explanation:

≔⁰η

Start with 0 as ⌊√1/10⌋.

FN«

Repeat n times.

≧×χη

Multiply by 10 as our first estimate of ⌊10ⁱ·√1/10⌋.

W﹪L×⊕η⊕η²≦⊕η

Increment our estimate until the number of digits of its square would become even, at which point it exactly equals ⌊10ⁱ·√1/10⌋.

»I⊕η

Increment the final estimate, resulting in ⌈10ⁿ·√1/10⌉ as required.

\$\endgroup\$
2
\$\begingroup\$

C (gcc), 22 bytes

f(n){n=exp10(n-.5)+1;}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 17 bytes

n=>-~(10**(n+.5))

Try it online!

Works up to \$n=8\$.


JavaScript (Node.js), 23 bytes

n=>(p=10**(n+.5)+1)-p%1

Try it online!

Works up to \$n=15\$.


JavaScript (Node.js), 40 bytes

n=>eval("for(i=0n;!('0'+i*i)[2*n];)++i")

Try it online!

Don't try it at home.

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 5 bytes

·<°tî

Port of @hyper-neutrino♦'s Jelly answer, so also outputs \$a(n)\$ based on \$n\$.

Try it online or verify all test cases.

Explanation:

·      # Double the (implicit) input-integer
 <     # Decrease it by 1
  °    # Take 10 to the power this input*2-1
   t   # Take the square-root of that
    î  # Ceil it
       # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

Vyxal, 7 bytes

d‹₀$e√⌈

Try it Online! or Verify the test cases

Explained

d‹₀$e√⌈
d‹        Double and increment
  ₀$e     To the power of 10
     √⌈   Square root and ceiling
\$\endgroup\$
2
  • \$\begingroup\$ Did you know there's a 300 rep bounty you're eligible for? \$\endgroup\$
    – lyxal
    Apr 9 at 1:42
  • \$\begingroup\$ yep, I just haven't posted it yet \$\endgroup\$
    – Steffan
    Apr 9 at 1:43
1
\$\begingroup\$

BQN, 9 bytes

⌈10⋆-⟜0.5

Try it at BQN online REPL

⌈           # ceiling of
 10⋆        # 10 to the power of
    -⟜0.5  # input minus 0.5
\$\endgroup\$
1
\$\begingroup\$

Husk, 7 bytes

⌈`^10-.

Try it online!

Uses formula: floor () of 10 to the power of (^) input minus (-) a half (.).


Husk, 9 bytes

€D⁰mȯLd□N

Try it online!

Calculates the number of digits (Ld) of the square () of each () number (N), and selects the index of the first () one that matches the input () doubled (D).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.