23
\$\begingroup\$

Given an input n, your program or function must output the smallest positive integer k such that n rounded to the nearest multiple of k is greater than n.

Example.

Given an input 20, the output value should be 3:

  • The nearest multiple of 1 is 20, which is not greater than 20.

  • The nearest multiple of 2 is 20, which is not greater than 20.

  • The nearest multiple of 3 is 21, which is greater than 20, so it is output.

Test Cases

#Input  #Output
2       3
4       5
6       4
8       3
10      4
12      7
14      3
16      6
18      4
20      3
22      4
24      5
26      3
28      5
30      4
32      3
34      4
36      8
38      3
40      6
42      4
44      3
46      4
48      5
50      3
52      6
54      4
56      3
58      4
60      7
62      3
64      5
66      4
68      3
70      4
72      11
74      3
76      6
78      4
80      3
82      4
84      5
86      3
88      5
90      4
92      3
94      4
96      7
98      3
1000    6

The output given any odd input should be 2.

Rules

  • n is a positive integer less than 2^32
  • rounding is performed such that if two multiples of k are equally distant from n, the greater one is chosen ("round halves up"). In this way, every odd n yields an output of 2.
  • This is , so shortest code in each language wins.
\$\endgroup\$
4
  • \$\begingroup\$ I've edited the format of your test cases to make it easier to read, and more concise. Let me know if you have any problems with this, or if any of the new examples are off. :) \$\endgroup\$
    – DJMcMayhem
    Aug 16, 2017 at 17:58
  • \$\begingroup\$ @Shaggy Done! I removed 500 odds and 450 evens from the list. \$\endgroup\$ Aug 16, 2017 at 19:08
  • \$\begingroup\$ Is there an oeis link for this sequence? \$\endgroup\$
    – James K
    Aug 17, 2017 at 22:45
  • \$\begingroup\$ @JamesK I did not find one when I searched earlier. Possibly someone with an OEIS account could make one? \$\endgroup\$ Aug 17, 2017 at 22:49

22 Answers 22

12
\$\begingroup\$

Python 3, 48 38 bytes

Edit: -10 bytes by using recursion

l=lambda x,y=2:y*(x%y>=y/2)or l(x,y+1)

Try it online!

\$\endgroup\$
9
\$\begingroup\$

Japt, 6 bytes

@<rX}a

Try it online!

Explanation:

@    <r X}a
XYZ{U<UrX}a
X              // X = 0; Increments when the condition in between {...} fails
   {     }a    // Return the first integer X where:
    U          //   The input
     <U        //   is less than the input
       rX      //     rounded to the nearest multiple of X
\$\endgroup\$
5
  • 2
    \$\begingroup\$ r is a builtin? o_o \$\endgroup\$ Aug 16, 2017 at 18:46
  • \$\begingroup\$ @EriktheOutgolfer: Japt also has built-ins for rounding up or down :) \$\endgroup\$
    – Shaggy
    Aug 16, 2017 at 18:55
  • 5
    \$\begingroup\$ I knew this feature would come in handy someday :D \$\endgroup\$ Aug 16, 2017 at 19:59
  • \$\begingroup\$ @Shaggy that's nuts! o_o_o \$\endgroup\$ Aug 17, 2017 at 8:52
  • \$\begingroup\$ @Oliver: This has me more convinced to get to grips with function methods, now - my own version of this was 7 bytes: o æ@<rX \$\endgroup\$
    – Shaggy
    Aug 17, 2017 at 10:59
7
\$\begingroup\$

MATL, 13 bytes

tQ:yy/Yo*<fX<

Try it online! Or verify all inputs from 1 to 1000.

Explanation

Consider input 6.

t      % Implicit input. Duplicate
       % STACK: 6, 6
Q:     % Add 1, range
       % STACK: 6, [1 2 3 4 5 6 7]
yy     % Duplicate top two elements
       % STACK: 6, [1 2 3 4 5 6 7], 6, [1 2 3 4 5 6 7]
/      % Divide, element-wise
       % STACK: 6, [1 2 3 4 5 6 7], [6 3 2 1.5 1.2 1 0.8571]
Yo     % Round to closest integer. Halves are rounded up
       % STACK: 6, [1 2 3 4 5 6 7], [6 3 2 2 1 1 1]
*      % Multiply, element-wise
       % STACK: 6, [6 6 6 8 5 6 7]
<      % Less than, element-wise
       % STACK: [0 0 0 1 0 0 1]
f      % Find: indices of nonzeros (1-based)
       % STACK: [4 7]
X<     % Minimum of vector. Implicit display
       % STACK: 4
\$\endgroup\$
5
\$\begingroup\$

Python 2, 35 bytes

f=lambda n,i=1:n%i*2/i or-~f(n,i+1)

Try it online!

\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6), 28 25 bytes

n=>g=x=>n%x>=x/2?x:g(-~x)
  • 3 bytes saved thanks to Arnauld.

Test it

o.innerText=(f=

n=>g=x=>n%x>=x/2?x:g(-~x)

)(i.value=64)();oninput=_=>o.innerText=f(+i.value)()
<input id=i type=number><pre id=o>

Or test all numbers from 1-1000 (Give it a minute to run):

f=n=>g=x=>n%x>=x/2?x:g(-~x);[2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,8,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,7,2,3,2,5,2,4,2,3,2,4,2,11,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,11,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,8,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,7,2,3,2,5,2,4,2,3,2,4,2,13,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,9,2,3,2,5,2,4,2,3,2,4,2,8,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,8,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,7,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,10,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,11,2,3,2,5,2,4,2,3,2,4,2,8,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,8,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,9,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,7,2,3,2,5,2,4,2,3,2,4,2,8,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,8,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,10,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,7,2,3,2,5,2,4,2,3,2,4,2,8,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,8,2,3,2,5,2,4,2,3,2,4,2,9,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,10,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,7,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,8,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,8,2,3,2,5,2,4,2,3,2,4,2,13,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,13,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,8,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,7,2,3,2,5,2,4,2,3,2,4,2,11,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,6,2,4,2,3,2,4,2,9,2,3,2,5,2,4,2,3,2,4,2,7,2,3,2,6,2,4,2,3,2,4,2,5,2,3,2,5,2,4,2,3,2,4,2,8,2,3,2,6].forEach((x,y)=>o.innerText+=`\n-----------------------------\n${(++y+"").padStart(7)}  |${(y=f(y)()+"").padStart(8)}  |  ${x==y}`)
<pre id=o>  Input  |  Output  |  Pass</pre>

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

Proton, 33 bytes

n=>[x for x:2..n+2if n%x>=x/2][0]

Try it online!

\$\endgroup\$
5
  • \$\begingroup\$ I don't know anything about Proton, but It seems you can save 3 bytes: Try it online! \$\endgroup\$
    – jferard
    Aug 17, 2017 at 10:25
  • \$\begingroup\$ Maybe a coincidence, but this is exactly the same as totallyhuman's solution...:p \$\endgroup\$ Aug 18, 2017 at 16:29
  • \$\begingroup\$ @EriktheOutgolfer We posted it at the same time (in fact I ninja'd him by a few seconds) with 37-byter, because Hyper borked the operators, and when he fixed them we both updated. \$\endgroup\$
    – Mr. Xcoder
    Aug 18, 2017 at 16:30
  • \$\begingroup\$ Uhh, I ninja'd you IIRC. :P \$\endgroup\$ Aug 18, 2017 at 16:38
  • \$\begingroup\$ @totallyhuman You ninja'd me with a 41-byter. I posted the 37-byter first and ninja'd you with that one by a few seconds. \$\endgroup\$
    – Mr. Xcoder
    Aug 18, 2017 at 16:41
4
\$\begingroup\$

Pyth, 12 11 bytes

hfgy%QTTm+2

Try it here.

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

Proton, 33 bytes

x=>[y for y:2..x+2if x%y>=y/2][0]

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ FWIW, why did you remove <!-- language: lang-python -->? \$\endgroup\$
    – Mr. Xcoder
    Aug 18, 2017 at 16:43
3
\$\begingroup\$

Jelly, 11 bytes

÷R%1<.¬;1TṂ

A monadic link taking and returning positive integers.

Try it online! or see a test suite.

How?

÷R%1<.¬;1TṂ - Link: number, n       e.g. 10
 R          - range(n)               [ 1,2,3     ,4  ,5,6     ,7     ,8   ,9     ,10]
÷           - n divided by           [10,5,3.33..,2.5,2,1.66..,1.42..,1.25,1.11..,1 ]
  %1        - modulo by 1            [ 0,0,0.33..,0.5,0,0.66..,0.42..,0.25,0.11..,0 ]
    <.      - less than 0.5?         [ 1,1,1     ,0  ,1,0     ,1     ,1   ,1     ,1 ]
      ¬     - not                    [ 0,0,0     ,1  ,0,1     ,0     ,0   ,0     ,0 ]
       ;1   - concatenate a 1        [ 0,0,0     ,1  ,0,1     ,0     ,0   ,0     ,0 , 1]
         T  - truthy indices         [            4    ,6                           ,11]
          Ṃ - minimum                4

Note: The concatenation of 1 is just to handle the cases where n is one of 1 ,2, or 4 when the result needs to be n+1 (‘R÷@%1<.¬TṂ would also work).

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

Haskell, 33 32 bytes

f n=[i|i<-[1..],2*mod n i>=i]!!0

Try it online!

Saved one byte thanks to w0lf

\$\endgroup\$
1
  • \$\begingroup\$ You can use !!0 instead of head \$\endgroup\$ Aug 17, 2017 at 8:28
2
\$\begingroup\$

Dyalog APL, 23 22 bytes

{⊃x/⍨⍵<x×⌊.5+⍵÷x←⍳1+⍵}

Try it online!

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

Pyth, 5 bytes

fgy%Q

Test suite

No rounding builtins, just checking for the first positive integer T, where double the input mod T is greater than or equal to T.

Explanation:

fgy%Q
fgy%QTT    Implicit variable introduction.
f          Find the first positive integer T such that the following is truthy:
   %QT     Input % T
  y        Doubled
 g    T    Is greater than or equal to T
\$\endgroup\$
0
2
\$\begingroup\$

x86 Machine Code, 17 bytes

This code implements a basic, iterative solution in the form of a reusable function:

31 F6                   xor    esi, esi
46                      inc    esi         ; set ESI (our temp register) to 1

                     Loop:
89 C8                   mov    eax, ecx    ; copy 'n' to EAX for division
46                      inc    esi         ; eagerly increment temp
99                      cdq                ; extend EAX into EDX:EAX
F7 F6                   div    esi         ; divide EDX:EAX by ESI
01 D2                   add    edx, edx    ; multiply remainder by 2
39 F2                   cmp    edx, esi    ; compare remainder*2 to temp
7C F4                   jb     Loop        ; keep looping if remainder*2 < temp

96                      xchg   eax, esi    ; put result into EAX (1 byte shorter than MOV)
C3                      ret

The function follows the fastcall calling convention, so that the single parameter (n) is passed in the ECX register. The return value (k) is, per usual, returned in the EAX register.

Try it online!

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

Java 8, 42 bytes

Lambda from Integer to Integer.

n->{for(int f=1;;)if(n%++f*2>=f)return f;}

Try It Online

Acknowledgments

  • -1 byte thanks to Kevin Cruijssen
\$\endgroup\$
1
  • 4
    \$\begingroup\$ You can save a byte by starting f=1 and using ++f on the first f, like this: n->{for(int f=1;;)if(n%++f*2>=f)return f;} \$\endgroup\$ Aug 17, 2017 at 7:54
1
\$\begingroup\$

Perl 5, 24 + 1 (-p) = 25 bytes

1while$_%++$k<$k/2;$_=$k

Try it online!

Tries each integer $k starting at 1 until it finds a remainder that is at least half of $k.

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

Forth (gforth), 45 bytes

: f 1 begin 1+ 2dup mod over 1+ 2/ >= until ;

Try it online!

Code Explanation

: f             \ start a new word definition
  1             \ start a counter at 1
  begin         \ start an indefinite loop
    1+          \ add 1 to counter
    2dup mod    \ duplicate input value and counter, get remainder of input/counter
    over 1+ 2/  \ get counter/2 (add 1 to force rounding up)
    >=          \ check if remainder is greater than counter/2
  until         \ end loop if true, otherwise go back to beginning
;               \ end word definition
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 9 bytes

∞.ΔIs/Dò‹

Try it online!

Explanation

∞.ΔIs/Dò‹ Full code
∞.Δ       Returns the first number for which the following code returns true
             -> stack is [n]
   Is     Push the input and swap the stack -> stack is [input, n]
     /    Divide both of them -> stack is [input/n]
      Dò  Duplicate and round the second -> stack is [input/n, rounded(input/n)]
        ‹ Check if input/n got larger by rounding -> stack is [bool]
             -> if bool is true, abort and return the current number
\$\endgroup\$
1
\$\begingroup\$

Rockstar, 681 bytes

Thought takes Patience and Control
While Patience is as high as Control
Let Patience be without Control

Give back Patience

Rock takes Art
Love is neverending
Sex is bottomless
Put Thought taking Art & Love into your head
If your head is Sex
Give back Art
Else
Limits are inspiration
Put Art with Limits without your head into the rubbish
Give back the rubbish


Listen to Chance
Questions are unstoppable
Until Questions is Chance
Build Questions up
Put Thought taking Chance, Questions into your mind
Answers are independence (but)
Put Questions over Answers into the world
Put Rock taking the world into the world
If your mind is as big as the world
Say Questions
Break it down

You can try rockstar online, but you'll need to copy and paste the code across. It will prompt you for an input number.

I didn't go for lowest byte count , because Rockstar is obviously not made for golfing, so instead I tried to go for Rock 'n' Roll lyrics.

Explanation:

This is based on the same solution as others (python, java):

Iterate up from 2:
if n % iterator >= ceil(n/2)
    return iterator

First I need to define modulus and ceiling functions though, which for poetry's sake are called Thought and Rock.

The below is a less poetic version with different variable names, and explanations where the syntax is unclear. Parentheses denote comments.

Modulus takes Number and Divisor
While Number is as high as Divisor
Put Number minus Divisor into Number
    (blank line ending While block)
Give back Number (return Number)
    (blank line ending function declaration)
Ceil takes Decimal
Put Modulus taking Decimal, 1 into Remainder
If Remainder is 0
Give back Decimal (return Decimal)
Else
Put Decimal with 1 minus Remainder into Result
Give back Result (return Result)
    (blank line ending if block)
    (blank line ending function declaration)
Listen to Input (Read from STDIN to Input)
Index is 1
Until Index is Input
Build Index up (Increment by 1)
Put Modulus taking Input, Index into LHS
Put Index over 2 into RHS
Put Ceil taking RHS into RHS
If LHS is as big as RHS
Say Index
Break it down (Break from loop)
\$\endgroup\$
0
\$\begingroup\$

Jelly, 18 bytes

ɓ÷Ḟ,¥Ċ$×ạÐṂ⁸Ṁ>⁸µ1#

Try it online!

Full program.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Full program. When is it not? \$\endgroup\$ Aug 16, 2017 at 18:57
  • \$\begingroup\$ @totallyhuman Sometimes it also works as a function. \$\endgroup\$ Aug 17, 2017 at 8:53
0
\$\begingroup\$

Swift 3, 51 bytes

{n in(2..<n+2).filter{Float(n%$0)>=Float($0)/2}[0]}

For some extremely bizarre reasons, [0] doesn't work online. Here is the online compiler-compatible version (that uses .first! instead):

{n in(2..<n+2).filter{Float(n%$0)>=Float($0)/2}.first!}

Test Suite (online-compatible).

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

C# (Mono), 39 bytes

n=>{int i=1;for(;n%++i*2<i;);return i;}

Try it online!

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

Stax, 7 bytes

ç&╬▼⌐╔ñ

Run and debug it

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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