7
\$\begingroup\$

Schlosberg Numbers

In issue 5 of Mathematical Reflections, Dorin Andrica proposed the problem of characterising the positive integers n such that \sum_{k=1}^n \lfloor \frac{n}{k} \rfloor is an even integer. Eight people submitted correct solutions showing that these are the integers n for which \lfloor \sqrt{n} \rfloor is even. The published solution was by Joel Schlosberg, so I call them the Schlosberg numbers.

These numbers may be found in OEIS as sequence A280682.

Your challenge is: given n, output the nth Schlosberg number. (0 or 1 indexed)

The first 50 Schlosberg numbers are: 0 4 5 6 7 8 16 17 18 19 20 21 22 23 24 36 37 38 39 40 41 42 43 44 45 46 47 48 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 100 101 102 103 104

Normal rules and the shortest code wins!

\$\endgroup\$
  • 1
    \$\begingroup\$ Why specifically the 1st 50? What about taking n and outputting a(n); outputting indefinitely; or taking n and outputting up to a(n)? \$\endgroup\$ – Jonathan Allan Apr 28 '18 at 18:51
  • \$\begingroup\$ @JonathanAllan True, I went with the first 50, because that was what I was testing when I wrote it myself. while there are only a few answers I shall change it \$\endgroup\$ – george Apr 28 '18 at 18:53
  • \$\begingroup\$ ..and what about the other options which are oft-used for sequence based challenges? \$\endgroup\$ – Jonathan Allan Apr 28 '18 at 18:56
  • 6
    \$\begingroup\$ FYI for next time, it's generally not recommended to update the requirements after answers have been posted. \$\endgroup\$ – Erik the Outgolfer Apr 28 '18 at 18:58
  • 1
    \$\begingroup\$ @EriktheOutgolfer yet asking for such specifics is bound to have people ask, so in this case, change, live & learn. \$\endgroup\$ – Jonathan Allan Apr 28 '18 at 18:59

24 Answers 24

7
\$\begingroup\$

Haskell, 32 bytes

(filter(even.floor.sqrt)[0..]!!)

Try it online!

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

Husk, 9 bytes

!fȯ¦2⌊√ΘN

Try it online!

Explanation

!f(¦2⌊√)ΘN  -- 1-indexed number, eg: 4
        ΘN  -- natural numbers with 0: [0,1,2,3,4,5,6,7,8,9..
 f(    )    -- filter by
  (   √)    -- | square root: [0,1,1.414213562373095,1.7320508075688774,2,2.23606797749979,2.449489742783178,2.6457513110645903,2.82842712474619,3,..
  (  ⌊ )    -- | floor: [0,1,1,1,2,2,2,2,2,3,..
  (¦2  )    -- | divisible by 2: [1,0,0,0,1,1,1,1,1,0,..
            -- : [0,4,5,6,7,8,..
!           -- get element: 6
\$\endgroup\$
4
\$\begingroup\$

Python 3, 42 bytes

f=lambda n,k=1:n and-~f(n-(k**.5%2<1),k+1)

Try it online!

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

Python 3, 49 bytes

def f(n):
 k=(1+(8*n+1)**.5)//4
 return n+2*k*k+k

Try it online!

A slightly different approach. First, if we subtract the sequence 0,1,2,... from the sequence of Schlosberg numbers, we get the sequence 0,3,3,3,3,3,10,10,10,10,10,10,10,10,10,21. Ignoring repetitions, the sequence 0,3,10,21,... is the sequence a(k) = 2k^2+k. If we can find k, the nth Schlosberg number is then n+a(k).

Given k, each a(k) is repeated 4k+1 times. Summing the length of the first k blocks, we get that the kth block of repetition ends at entry n=2k^2-k. Inverting this, we get k=(1+sqrt(8n+1))/4, which gives an explicit formula for k.

\$\endgroup\$
  • \$\begingroup\$ @Reesi82 def f(n):k=(1+(8*n+1)**.5)//4;return n+2*k*k+k saves three bytes of whitespace. In Python 2, you could replace return with print. \$\endgroup\$ – Dennis May 1 '18 at 16:24
3
\$\begingroup\$

J, 22 bytes

{.[:I.0=2|3<.@%:@i.@*]

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer, however I have updated the requirements to output the nth number. sorry for the inconvenience \$\endgroup\$ – george Apr 28 '18 at 18:56
  • 1
    \$\begingroup\$ @george - updated \$\endgroup\$ – Galen Ivanov Apr 28 '18 at 19:17
3
\$\begingroup\$

R, 37 bytes

function(n)(x=0:n^2)[!x^.5%/%1%%2][n]

Try it online!

1-based indexing.

\$\endgroup\$
3
\$\begingroup\$

mIRC Scripting, 171 bytes

a {
  %s = 0
  %x = -1
  while 1 {
    inc %x 2
    %i = %x
    while %i {
      echo - %s
      inc %s
      dec %i
    }
    inc %x 2
    inc %s %x
  }
}

I didn't yet see this method for generating new Schlosberg numbers, so above is just a simple one that reads like pseudocode. We start at 0, display 1 number, increase 3, display 5, increase 7, display 9, etc. A simple pattern emerges.

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

Jelly, 7 bytes

½ḞḂ¬Ʋ#Ṫ

A full program accepting n from STDIN

Try it online!

How?

½ḞḂ¬Ʋ#Ṫ - Main link: no arguments
     #  - take input (n) from STDIN & count up (i=0,1,...) collecting truthy results of:
    Ʋ   -   last four links as a monad:
½       -     square root
 Ḟ      -     floor      (½Ḟ could also be ƽ - integer square root)
  Ḃ     -     bit (modulo by 2 - i.e. isOdd?)
   ¬    -     logical NOT
      Ṫ - tail (get the nth rather than the first n)
        - implicit print to STDOUT
\$\endgroup\$
2
\$\begingroup\$

Pyth, 10 bytes

e.fiI2s@Z2

Try it here!

Explanation

e.fiI2s@Z2 – Full program.
 .f        – Find the first N positive integers satisfying the requirements (var: Z).
e          – And take the last one (i.e. the Nth).
       @Z2 – Take the square root of Z.
      s    – Convert to an integer.
   iI2     – Check if 2 is invariant over applying GCD with the above (i.e. is it even?)
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 5 bytes

µNtóÈ

Try it online!

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

Japt, 11 bytes

0-indexed

_¬f v «U´}a

Try it


Explanation

                :Implicit input of integer U
_        }a     :Return the first integer that returns true when passed through the following function
 ¬              :  Square root
  f             :  Floor
    v           :  Divisible by 2?
      «U´       :  If the above is true then postfix decrement U and check if it's falsey (0)
\$\endgroup\$
2
\$\begingroup\$

JavaScript, 36 34 bytes

0-indexed

n=>(g=i=>i**.5&1||n--?g(++i):i)(0)

2 bytes saved thanks to l4m2


Test it

o.innerText=[...Array(50).keys()].map(
n=>(g=i=>i**.5&1||n--?g(++i):i)(0)
).join`, `
<pre id=o></pre>

\$\endgroup\$
1
\$\begingroup\$

Ruby, 45 44 42 bytes

->n,i=-1{(i+=1)**0.5%2<1||n+=1while n>i;i}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

APL+WIN, 29 26 bytes

3 bytes saved thanks to Cows quack

Prompts for integer input:

(0,(~2|⌊r*.5)/r←⍳n×3)[n←⎕]

Explanation:

[n←⎕] prompts for input and selects the nth value of the result

(0,(~2|⌊r*.5)/r←⍳n×3)[n←⎕] create a vector of all results up to n×3
which works up to limit of machine. ×2 works up to n~10E7
\$\endgroup\$
  • \$\begingroup\$ Would (0,(~2|⌊r*.5)/r←⍳n×3)[n←⎕] work? \$\endgroup\$ – Kritixi Lithos Apr 29 '18 at 10:24
  • \$\begingroup\$ @Cowsquack. It would indeed for a 3 byte saving. Thanks. \$\endgroup\$ – Graham Apr 29 '18 at 10:28
1
\$\begingroup\$

Jelly, 9 bytes

ḤḶ²Ḷœ^/ị@

Try it online!

Unfortunately it's longer than the other answer, but I do like this approach.

Explanation

The goal is to get the ranges from each even square to each subsequent odd square, excluding the odd square. We can do this by taking the symmetric set difference of some even number of ranges from zero to just below each square.

Ḥ   Double the input N to ensure it's even.
Ḷ   Lowered range, from 0 to 2N-1.
²   Square to get the first 2N squares.
Ḷ   Get the lowered ranges up to each square.
œ^/ Fold symmetric set difference over the ranges.
ị@  Select the Nth value.
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 34 bytes

_=>_+2*(a=~~(1+(8*_+1)**.5)/4)*a+a

Try it online!


Inspired by @Reesi82's answer

\$\endgroup\$
1
\$\begingroup\$

Ruby, 39 38 bytes

->n{(0..n*4).select{|x|x**0.5%2<1}[n]}

Try it online!

0-indexed. Instead of simple looping, this approach takes a large enough sequence of numbers and selects only those that fulfill the condition. The particular multiplier n*4 is necessary to cover the case n=1 => 4 (n*n doesn't fit here), and due to the pattern in the sequence, the value of the nth number fluctuates around n*2, so taking n*4 should always be large enough.

\$\endgroup\$
1
\$\begingroup\$

C (gcc), 57 56 bytes

  • Saved a byte thanks to ceilingcat; golfed e>=++b*b to e/++b/b.
b,e;r(g){for(e=0;g&&++e;b&1&&--g)for(b=0;e/++b/b;);g=e;}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

These answers are not the most efficient ways to solve the problem, however I do think they are interesting.

Haskell, 37 33 bytes

(!!)$do x<-[0,2..];[x^2..x^2+2*x]

Try it online!

Haskell, 45 42 bytes

y#x=not$y^2>x||(y+1)#x
(filter(0#)[0..]!!)

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ You're better off using do in cases like this \$\endgroup\$ – H.PWiz Jun 21 '18 at 16:38
  • 1
    \$\begingroup\$ Also (x+1)^2-1 = x^2+2*x \$\endgroup\$ – H.PWiz Jun 21 '18 at 16:44
  • \$\begingroup\$ @H.PWiz Thanks! I tried a do, but I didn't know you could use a semicolon like that. \$\endgroup\$ – Wheat Wizard Jun 21 '18 at 17:21
0
\$\begingroup\$

JavaScript (ES6), 41 40 bytes

f=(n,i=0,j=1)=>n<j?n+i:f(n-j,i-2*~j,j+4)
<input type=number min=0 value=0 oninput=o.textContent=f(this.value)><pre id=o>0

Edit: Saved 1 byte thanks to @JonathanFrech.

\$\endgroup\$
  • \$\begingroup\$ i+j+j+2 <=> i-~j*2. \$\endgroup\$ – Jonathan Frech Apr 28 '18 at 20:31
0
\$\begingroup\$

Perl 6, 27 bytes

{grep(+^*.sqrt%2,0..*)[$_]}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Forth (gforth), 81 bytes

Sequence is 1-indexed [f(1) is 0]

: f 0 0 begin over s>f fsqrt f>s 1 and 0= - 1 under+ dup 3 pick = until drop 1- ;

Try it online!

Explanation

0 0              \ place the loop index and sequence index on the stack
begin            \ start an indefinite loop
   over          \ grab a copy of the loop index
   s>f sqrt f>s  \ get the square root of the index and truncate
   1 and 0=      \ determine if result is even
   -             \ if even, add 1 to sequence tracker (-1 is default for "true" in forth)
   1 under+      \ add 1 to the loop index
   dup 3 pick =  \ check if the current sequence position is the one that was requested
until            \ end the loop if condition above is true
drop 1-          \ drop the loop index and subtract 1 from the loop index to get the result
\$\endgroup\$
0
\$\begingroup\$

dc, 31 bytes

sn_1[d]sD[1+dv2%0=Dzln!<M]dsMxp

Try it online! (1-indexed)

Rather simple. D is a macro that just duplicates the top-of-stack. We begin by storing the user's input in n, and placing negative 1 (_1) on the stack. Macro M increments the top-of-stack by one, duplicates it, and then does the necessary sqrt mod 2 (v2%). dc's precision is zero by default, so doing a square root is, by default, actually the floor of the square root. 0=D compares our v2% to zero, and runs our duplication macro (D) if true. z fetches the stack depth, and then ln!<M compares this to n (our target), continuing to run M until we get to the value we were looking for. Finally, print it.

\$\endgroup\$
0
\$\begingroup\$

Tcl, 84 bytes

proc S {x n\ 0 i\ 1} {while \$i<$x {if 1>int(floor([incr n]**.5))%2 {incr i}}
set n}

Try it online!

\$\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.