[Question]
  [
Part of [**Advent of Code Golf 2021**](https://codegolf.meta.stackexchange.com/q/24068/78410) event. See the linked meta post for details.
Related to [AoC2015 Day 20](https://adventofcode.com/2015/day/20), Part 1.
*[Here's why I'm posting instead of Bubbler](https://chat.stackexchange.com/transcript/240?m=59765196#59765196) [and why not emanresuA](https://chat.stackexchange.com/transcript/message/59777290#59777290)*
---
To keep the Elves busy, Santa has them deliver some presents by hand, door-to-door. He sends them down a street with infinite houses numbered sequentially: 1, 2, 3, 4, 5, and so on.
Each Elf is assigned a number, too, and delivers presents to houses based on that number. Instead of giving out presents at fixed intervals, Santa decides to give them out in longer and longer intervals because apparently he's short of supplies right now. Ignore the fact that [the total number of presents delivered is the same after all](https://en.wikipedia.org/wiki/Aleph_number#Aleph-nought) :P
* The first Elf (number 1) delivers presents to the houses numbered 1, 1+2, 1+2+3, 1+2+3+4, 1+2+3+4+5, ... (1, 3, 6, 10, 15, ...)
* The second Elf (number 2) delivers presents to the houses numbered 2, 2+3, 2+3+4, 2+3+4+5, 2+3+4+5+6, ... (2, 5, 9, 14, 20, ...)
* Elf number 3 delivers presents to houses 3, 3+4, 3+4+5, ... (3, 7, 12, 18, 25, ...)
* ...
There are infinitely many Elves, numbered starting with 1. Each Elf delivers exactly 1 present at each house.
So, the first nine houses on the street end up like this:
* House 1 gets 1 present (by Elf 1).
* House 2 gets 1 present (by Elf 2).
* House 3 gets 2 presents (by Elves 1 and 3).
* House 4 gets 1 present (by Elf 4).
* House 5 gets 2 presents (by Elves 2 and 5).
* House 6 gets 2 presents (by Elves 1 and 6).
* House 7 gets 2 presents (by Elves 3 and 7).
* House 8 gets 1 present (by Elf 8).
* House 9 gets 3 presents (by Elves 2 (2+3+4), 4 (4+5), and 9).
So the lowest-numbered house that gets at least 3 presents is House 9.
Given a positive number `n`, what is the lowest house number that will get at least `n` presents?
Standard [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") rules apply. The shortest code in bytes wins.
## Test cases
```
n -> answer
1 -> 1
2 -> 3
3 -> 9
4 -> 15
5 -> 45
6 -> 45
7 -> 105
8 -> 105
9 -> 225
10 -> 315
12 -> 315
17 -> 1575
25 -> 10395
```
  
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), 32 bytes
```
n->i=1;while(numdiv(i)<n,i+=2);i
```
[Try it online!](https://tio.run/##FcdBDoJADADArzSc2tAldhPjAZePEA4bBG2CtSEo4fWr3mY8rxruXmZIxUKnSdr9ocuE9n7e9INKV2OtU6RWS3ZfDjQIHfiqtv1Y/VPBjEbEML5szBv20jRyGhh6iQxyYYjngah8AQ "Pari/GP – Try It Online")
House \$i\$ gets a present from elf \$j\$ \$\iff\$ \$i=\frac{k(j+k-1)}{2}\$ for some \$k \ge 0\$ \$\iff\$ \$k=\frac{\sqrt{(2j-1)^2+8i}-2j+1}{2}\$ for some \$k\$ \$\iff\$ \$(2j-1)^2+8i=l^2\$ for some \$l\$ \$\iff\$ \$8i=(l+2j-1)(l-2j+1)\$ for some \$l\$ \$\iff\$ \$m-8i/m=4j-2\$ for some divisor \$m\$ of \$8i\$.
So house \$i\$ gets \$n\$ presents \$\iff\$ \$8i\$ has \$n\$ divisors \$d\$ such that \$d\equiv 2 \pmod{4}\$ \$\iff\$ \$i\$ has \$n\$ odd divisors.
But \$i\$ and \$2i\$ has exactly the same number of odd divisors. So we only need to consider the odd numbers, whose divisors are all odd.
[Answer]
# JavaScript (ES7), 65 bytes
```
f=(n,k)=>(g=n=>n&&!((4*n*--n+8*k+1)**.5%1)+g(n))(k)>=n?k:f(n,-~k)
```
[Try it online!](https://tio.run/##FYxBDoIwEADvvmI9SHbLllgFQU3ryVcYDwQpasnWgPHo1xEPc5rMPOtPPTbD4/XWEm/tNHmLwoGsw86KdZIkS8RcidJa0kqF1JBSWbEylHYoRBjIWTmFg587/Q00HS9gGDYMW4acoWDYMZQMFcOewaxnZmlKuGY@Due6uaOAdQuAJsoY@zbrY4f@P1/Q9AM "JavaScript (Node.js) – Try It Online")
### How?
The formula giving the \$x\$-th house visited by Elf number \$n\$ is:
$$H\_n(x) = \frac{x(x+2n-1)}{2}$$
We want to know whether Elf number \$n\$ is going to visit some house \$k\$, i.e. if there's some \$x>0\$ such that \$H\_n(x)=k\$. It means that we have to check if the following quadratic equation has a positive integer solution:
$$\frac{1}{2}x^2+\left(n-\frac{1}{2}\right)x-k=0$$
The determinant is:
$$\Delta = \left(n-\frac{1}{2}\right)^2+2k=n^2-n+2k+\frac{1}{4}$$
Leading to:
$$4\Delta = 4n^2-4n+8k+1 = 4n(n-1)+8k+1$$
$$2\sqrt{\Delta} = \sqrt{4n(n-1)+8k+1}$$
Leading to a unique positive value of \$x\$:
$$x=\frac{\sqrt{\Delta}+1}{2}-n$$
But the only thing we're interested in is to know whether this \$x\$ is an integer. So we just test whether \$\sqrt{4n(n-1)+8k+1}\$ is an integer (which — if it is — is always odd).
Hence the JavaScript test:
```
!((4 * n * --n + 8 * k + 1) ** 0.5 % 1)
```
---
# JavaScript (ES6), 57 bytes
This one is a port of [alephalpha's great method](https://codegolf.stackexchange.com/a/238053/58563).
```
f=(n,i=1)=>eval("for(d=n,k=i;k;)d-=i%k--<1")>0?f(n,i+2):i
```
[Try it online!](https://tio.run/##FY1LDoIwGIT3nGJCYmzDX0IRfGHrylMYFw0PrZDWgOH6tS5mFt9MZt5mNUs7289XON/1IQyKObJKcqX71UwsHfzMOuVoVLYZG94JZTejEBeZcl1ch387K/nZhuYOSSgJO0JFqAl7woFwJJwIsoiKoYykrPHI4@7NtC/moHQCtN4tfurzyT8jyrCF0NEyxAfOEx5@ "JavaScript (Node.js) – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 9 bytes
Another port of [alephalpha's approach](https://codegolf.stackexchange.com/a/238053).
```
∞·<.ΔÑg›_
```
[Try it online!](https://tio.run/##yy9OTMpM/f//Uce8Q9tt9M5NOTwx/VHDrvj//40B "05AB1E – Try It Online")
A direct brute force approach is a byte longer:
```
∞.ΔLŒOy¢›_
```
[Try it online!](https://tio.run/##yy9OTMpM/f//Ucc8vXNTfI5O8q88tOhRw674//@NAQ "05AB1E – Try It Online")
```
∞           -- infinite list of positive integers
 ·<         -- double and decrement each; this yields the odd integers
   .Δ       -- find the first value that satisfies:
     Ñg     --   the number of divisors ...
       ›_   --   ... is not less than the input
∞.Δ         -- find the first positive integer y that satisfies:
   L        --   range from 1 to y
    ŒO      --   the sums of each contiguous sublist
            --   these are all of the form sum(a..b) for 1<=a<b<=y
      y¢    --   count the occurrences of y in the sums
        ›_  --   is this not less than the input?
```
[Answer]
# [R](https://www.r-project.org/), 42 bytes
Or **[R](https://www.r-project.org/)>=4.1, 35 bytes** by replacing the word `function` with `\`.
```
function(n){while(sum(!T%%1:T)<n)T=T+2;+T}
```
[Try it online!](https://tio.run/##K/qfZvs/rTQvuSQzP08jT7O6PCMzJ1WjuDRXQzFEVdXQKkTTJk8zxDZE28haO6T2f4VtsoahlaGBjqGRjqG5jpGpJldxaolfYm5qsUZOYkFBTqVGhU6apk6F5n8A "R – Try It Online")
Another port of [@alephalpha's solution](https://codegolf.stackexchange.com/a/238053/55372).
[Answer]
# [Husk](https://github.com/barbuz/Husk), ~~10~~ ~~9~~ 8 bytes
*Edit: -2 bytes thanks to hint from ovs*
```
ḟȯ≥⁰LḊİ1
```
[Try it online!](https://tio.run/##ASMA3P9odXNr/23igoHhuKMxMP/huJ/Ir@KJpeKBsEzhuIrEsDH//w "Husk – Try It Online")
An alternative [Husk](https://github.com/barbuz/Husk) approach to [rues' answer](https://codegolf.stackexchange.com/a/238066/95126), here porting [alephalpha's method](https://codegolf.stackexchange.com/a/238053/95126).
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 25 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
[N.µxtExNNn-+N·%>½}¾¹@i,q
```
[Try it here!](https://tio.run/##yy9OTMpM/f8/2k/v0NaKEtcKP788XW2/Q9tV7Q7trT2079BOh0ydwv//jUwB)
**Decomposition:**
```
func(n) - Number of presents for a given house 'n'
xt                          # s_max = sqrt(2n)
  E           }             # for s in 1..s_max
   xNNn-+N·                 # n, 2n+s-s^2, 2s
           %>               # if 2n-s^2+s % 2s = 0
             ½              # increment present counter
               ¾            # return present counter
main
[                           # loop n=0..infinity
 N                          # push house number to stack
  .µ                        # reset present counter to zero
    xtExNNn-+N·%>½}¾        # func(n)
                    ¹@      # if func(n) >= p:
                      i,q   # print N, quit
```
**Explanation:**
I wanted to find a mathematical approach rather than a computational one, and I'm decently pleased with what I found.
Found through very unscientific means, but works for all numbers I've tested.
Making a scatter plot between elf number \$r\$ and house number \$h\$ reveals some nice patterns.
Distinct straight lines are formed, which I have named 'series'.
Where these series have integer pairs \$(r,h)\$, a house receives one present.
An equation was formed to define these series by number:
$$ n = sr + \frac{s^2-s}{2} $$
Solving for \$r\$ gives:
$$ r = \frac{2n-s^2+s}{2s} $$
Integer solutions for \$r\$ mean that elf \$r\$ visited house \$n\$ on series \$s\$.
$$ (2n-s^2+s) \equiv 0 \pmod {2s} $$
means a present was left.
All that remains is to iterate over all series for a house to count a number of presents.
A maximum series number is defined:
$$ s\_{max}= \lfloor \sqrt{2n} \rfloor $$
derived approximately from the h-intercept of each series being
$$ r = \frac{s(s+1)}{2} $$
This ensures that \$r \geq 1\$.
Iterate over series \$1\$ though \$\sqrt{2n}\$ for each house to determine number of presents.
Iterate over houses with this function until finding one with sufficient presents!
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 45 bytes
```
Ｎθ≔⁰ηＷ‹№υηθ«≦⊕η≔⟦⟧υＦη«≔⁰ζＷ‹ζη«≦⊕κ≧⁺κζ»⊞υζ»»Ｉη
```
[Try it online!](https://tio.run/##dY@9DoIwEIDn9ik6tgkmJo5MholECXE1DhUrbSwF@qMJhmevLWBwcbjh7rvvfipOddVS6X2uOmcL11yZxj1J4d4YUSu8TRAP2YsLyRA@MGNw1jplsYsgQT0h6A3BkXaLkKtKs4Ypy26zChZwviTIxfzeaoT5pIF1yxAR@N0zRH9u@zf/MUkrPYmaW1xKZwL7zhxDlM7wePJUGeEISy3CExk1NpxCUu93fvOUHw "Charcoal – Try It Online") Link is to verbose version of code. Explanation: Brute force because I'm too tired to work out a formula.
```
Ｎθ
```
Input `n`.
```
≔⁰η
```
Start at house `0`.
```
Ｗ‹№υηθ«
```
Repeat until `n` visits have been found.
```
≦⊕η
```
Try the next house.
```
≔⟦⟧υ
```
Start building up the list of houses visited by the elves.
```
Ｆη«
```
Loop over enough elves so that the last elf visits the house. (Note that these elves are 0-indexed.)
```
≔⁰ζ
```
Start at house `0`.
```
Ｗ‹ζη«
```
Repeat until the current house has been reached or passed.
```
≦⊕κ
```
Increase the gap between houses.
```
≧⁺κζ
```
Visit the next house.
```
»⊞υζ
```
Save the house the elf ended up visiting.
```
»»Ｉη
```
Output the found house.
Porting @alephalpha's method takes 22 bytes:
```
Ｎθ≔¹ηＷ‹ＬΦη¬﹪η⊕κθ≧⁺²ηＩη
```
[Try it online!](https://tio.run/##JYxBCsIwEEX3niLLCcSFddmVCELBluINYhsywTRpMxM9fkzpX3x48HgT6jRF7Uvpwpp5yMvbJNhke7oRORvgogRW@qHzRsDTENULlhEeznN1UYkhMvRxzj7u1IUpmcUENjN85D4lNilFr9ej@XIWGUafSYnmyI/JBYa7JgaUsi3lWs5f/wc "Charcoal – Try It Online") Link is to verbose version of code. Explanation:
```
Ｎθ
```
Input `n`.
```
≔¹η
```
Start at house `1`.
```
Ｗ‹ＬΦη¬﹪η⊕κθ
```
While the current house has fewer than `n` divisors (which must all be odd)...
```
≧⁺²η
```
... visit the next house but one.
```
Ｉη
```
Output the found house.
[Answer]
# [Rust](https://www.rust-lang.org/), 65 64 bytes
```
|n|{let mut i=1;while(1..=i).filter(|j|i%j<1).count()<n{i+=2};i}
```
[Try it online!](https://tio.run/##VZDRboMwDEXf@Qr3YVPSRqgJpR2ifEk1TWxLNlfU1UJQH4BvT4M2suKne@yra9m2a503BJcaiXHok0Y7MFCBH2joJ7h0DrCS5e0bG81kmlbIU4ON05YN5wGfzkfJ049rR47xI/W4qdRY4ujLxFwtMBJQU3vTlgMSPJ8SCMWkAMnFr1YCsllnAopZ74InnyEXsIuwf4RDsG0jvSyoEKBUJLkNm/4jpVriFJQfIqt8isqKufEavgN/9fn@tXq4rIyDum21dW/6Z8UMWxMXsF54xmT0/g4 "Rust – Try It Online")
* -1 byte by using `<1` instead of `==0` (thanks @Kevin Cruijssen)
[Answer]
# [Python 3](https://docs.python.org/3/), 62 bytes
```
f=lambda n,v=1:v*(sum(v%-~u<1for u in range(v))>=n)or f(n,v+2)
```
[Try it online!](https://tio.run/##K6gsycjPM/7/P802JzE3KSVRIU@nzNbQqkxLo7g0V6NMVbeu1MYwLb9IoVQhM0@hKDEvPVWjTFPTzjZPEyiYpgFUrm2k@R@kIhOhwlBHwdBQ04qLs6AoM69EI1MHqDJTU/M/AA "Python 3 – Try It Online")
---
# [Python 3](https://docs.python.org/3/), 76 bytes
```
lambda n:next(v for v in range(3**n)if sum(v%u<1for u in range(1,v+1,2))>=n)
```
[Try it online!](https://tio.run/##TckxDoMwDADAmb7CSyUbsrhsCPqSLqkgrSUwKCQRvD6ICW69ZQ//Wevsuk8e7fTtLWijwxYwgZs9JBAFb/U3YF2WSuJgjROmZ2z5/Hg9m1SxeRG9O6V8ptwTmKl5FIsXDSgGHApRPgA "Python 3 – Try It Online")
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 52 32 bytes
```
1//.i_/;0~DivisorSigma~i<#:>i+2&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b731BfXy8zXt/aoM4lsyyzOL8oODM9N7Eu00bZyi5T20jtf0BRZl5JdFq0YWwsF4xtgsQ2NIiN/Q8A "Wolfram Language (Mathematica) – Try It Online")
*-20 bytes thanks to att! Also thanks to ovs.*
Based off [alephaleph's excellent insight](https://codegolf.stackexchange.com/a/238053/15469), and probably not a great Wolfram golf but I couldn't resist those builtins. I'll look forward to att setting me straight.
[Answer]
# [Husk](https://github.com/barbuz/Husk), ~~14~~ 12 bytes
Fixed a bug and saved 3 bytes thanks to Dominic Van Essen!
```
ḟo≥⁰S#ȯṁ∫ṫḣN
```
[Try it online!](https://tio.run/##ATkAxv9odXNr/23igoH/4bifb@KJpeKBsFMjyK/huYHiiKvhuavhuKNO////WzEsMiwzLDQsNSw2LDcsOF0 "Husk – Try It Online")
[Answer]
# [Ruby](https://www.ruby-lang.org/), 66 bytes
```
->n,*r{w=[];1.step.find{|x|w+=r=[0,*r].map{|y|y+x};w.count(x)>=n}}
```
[Try it online!](https://tio.run/##FcpLCoAgFADAq7QKzXrkOp4XCRf9hBaZWKGint1qPWOfORSFpRO6bWx0OMqBw3VvBtSu15h8cgwtjv3HEo7JxBRSYD4PDpbz0TfxVKDOuZiKcADe03@RWtHyAg "Ruby – Try It Online")
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 11 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
```
@>Xâ Ê*Xu}f
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QD5Y4iDKKlh1fWY&input=WzEsMiwzLDQsNSw2LDcsOCw5LDEwLDEyLDE3LDI1XS1t)
Port of @alephalpha answer.
[Answer]
# TI-Basic, 32 bytes
```
Input N
1
While N>sum(seq(not(IfPart(Ans/I)),I,1,Ans
Ans+2
End
Ans
```
Port of [alephalpha's solution](https://codegolf.stackexchange.com/a/238053/58563). Output is stored in `Ans` and displayed.
[Answer]
# Python3, 162 bytes:
```
r=range
q=lambda h,n,l:any(i==h for i in l if i and l.count(i)>=n)
f=lambda n,h=1:h if(v:=q(h,n,[sum(r(x,y+1))for x in r(1, h+1)for y in r(1, h+1)]))else f(n,h+1)
```
A basic brute-force approach.
[Try it online](https://tio.run/##VY7BCsIwDIbve4ocUyzCEEQG8UXEQ3WrLXRZl22yPn1tBQ/mlHz8@ZKYVjfx6RIlZyEx/BqamYIZH70Bp1mHznBCT@TATgIePEMAb0tnuIdwfE4br@jVlVg19rfK2lHbuRLEd0czVtVt2UYU3HU6tEpV215tgq0GV1Al6Y/clRrCMoDF4itzjuLLseCXFUcT0Wr4vlzzZ1UqfwA).
[Answer]
# Java, 73 bytes
```
n->{int r=1,c=1,j;for(;c<n;)for(r+=2,c=j=1;j<r;)if(r%j++<1)c++;return r;}
```
Port of [*@alephalpha*'s Pari/GP answer](https://codegolf.stackexchange.com/a/238053/52210).
[Try it online.](https://tio.run/##fZDBasMwDIbvfQoRGNh4DbGhFOpkb7Beehw7eG4y7KVOUZzCKHn2TM6ynkYO/rGlT78ke3MzW3/@mmxr@h5ejQv3DYALscbG2BqO6TkHwLKkgWuKjBuSPproLBwhQDWF7cs95bGSz5aO102HTNsyaJ5uKCpFCV9J7UvU3DUMn7wQpeRWCI11HDAA6nHSyfs6fLTkvbS4de4MFxqOnSK68Pn2bvjvYMk6tXXkC66UBakQfM4BnL77WF/yboj5lepiG5gT2QEgEyGnffi8zL9cJovDgslilVMPTq1y@we3X@PU7o9TO7589jj9AA)
**Explanation:**
```
n->{              // Method with integer as both parameter and return-type
  int r=1,        //  Result-integer `r`, starting at 1
      c=1,        //  Count-integer, starting at 1
      j;          //  Temp integer, uninitialized
  for(;c<n;)      //  Loop as long as the count is smaller than the input:
    for(r+=2,     //   Increase `r` by 2
        c=j=1;    //   Reset the count to 1,
        j<r;)     //   Loop `j` in the range [1,r):
      if(r%j++<1) //    If `r` is divisible by `j`:
                  //    (and increase `j` by 1 afterwards with `j++`)
        c++;      //     Increase the count by 1
  return r;}      // After the nested loops: return the result
```
[Answer]
# TypeScript Types, 302 bytes
```
//@ts-ignore
type a<N,M=[]>=N extends M["length"]?M:a<N,[...M,0]>;type b<N,E,C,M=[]>=M extends N?[...C,0]:M extends[...N,...0[]]?C:b<N,[...E,0],C,[...M,...E]>;type c<N,M=[0],C=[0]>=N extends M?C:c<N,[...M,0],b<N,M,C>>;type d<N,M=[0]>=c<M>extends[...N,...0[]]?M["length"]:d<N,[...M,0]>;type M<X>=d<a<X>>
```
[Try It Online!](https://www.typescriptlang.org/play?#code/PTACBcGcFoEsHMB2B7ATgUwFDgJ4Ad0ACAQwB4A5AGgFkBeAbQF0A+W8w9AD3HUQBNIhavQBEAG17xwACxGMA-NQBcZKvQB0m6pQAMLANy4ChAEYVKAUUoBhGgxa1qHbrwGFy8jZtt6lTrjz8kF7qVJrqOkwK1kpmauFWejaUIdoJBkZEAMbmdPRJ1gx6rOwBroLU8jE58Vq6jJRxNDbMzIb4RHy5RQ451MxlQSFhmpGMCsLikjJySl216trF7cbUpAAarF1km8yY2B2EACoAjIS0QqQnbZgghPcAevIHxkcATOeXbzd3j8+ZxwAzJ81oCfsB7oQni8iEcACwg0hw8GQ6EAo4AVkRGJRfxhxwAbIiCbiof9DkcAOyIymktEUgAciIZdOeQA)
## Ungolfed / Explanation
```
type NumToTuple<N,M=[]> = N extends M["length"] ? M : NumToTuple<N,[...M,0]>
type CheckElf<HouseNum, NumToAdd, PresentCount, Sum=[]> = 
  Sum extends HouseNum
    // If Sum == HouseNum, return ElfCount + 1
    ? [...PresentCount, 0]
    : Sum extends [...HouseNum, ...0[]]
      // Otherwise, if Sum >= HouseNum, return ElfCount
      ? PresentCount
      // Othwerise, add NumToAdd to Sum, increase NumToAdd, and recurse
      : CheckElf<HouseNum, [...NumToAdd, 0], PresentCount, [...Sum, ...NumToAdd]>
type CountPresents<HouseNum, ElfNum=[0], PresentCount=[0]> =
  HouseNum extends ElfNum
    // If HouseNum == ElfNum, return PresentCount
    ? PresentCount
    // Otherwise, check this elf, add one to ElfNum, and recurse
    : CountPresents<HouseNum, [...ElfNum,0], CheckElf<HouseNum, ElfNum, PresentCount>>
type FindHouse<PresentMin, HouseNum=[0]> =
  CountPresents<HouseNum> extends [...PresentMin,...0[]]
    // If the number of presents at this house is >= the minumum, return this house number
    ? HouseNum["length"]
    // Otherwise, check the next house number
    : FindHouse<PresentMin,[...HouseNum,0]>
type Main<X> = FindHouse<NumToTuple<X>>
```
]