# AoCG2021 Day 4: Infinite Elves and infinite houses 2

Part of Advent of Code Golf 2021 event. See the linked meta post for details.

Related to AoC2015 Day 20, Part 1.

Here's why I'm posting instead of Bubbler and why not emanresuA

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 :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 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

• +1 for posting at 00:00:00Z ^^ Dec 4 '21 at 0:38

# Pari/GP, 32 bytes

n->i=1;while(numdiv(i)<n,i+=2);i


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.

• So this is to A038547 as A061799 is to A005179?
– Neil
Dec 4 '21 at 5:35

# 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!

### 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}$$

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

f=(n,i=1)=>eval("for(d=n,k=i;k;)d-=i%k--<1")>0?f(n,i+2):i


Try it online!

# 05AB1E, 9 bytes

Another port of alephalpha's approach.

∞·<.ΔÑg›_


Try it online!

A direct brute force approach is a byte longer:

∞.ΔLŒOy¢›_


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?


# R, 42 bytes

Or R>=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!

Another port of @alephalpha's solution.

# Husk, 109 8 bytes

Edit: -2 bytes thanks to hint from ovs

ḟȯ≥⁰LḊİ1


Try it online!

An alternative Husk approach to rues' answer, here porting alephalpha's method.

• You can save at least 2 bytes by only looking at odd numbers (İ1) like alephalpha's answer
– ovs
Dec 4 '21 at 15:53
• @ovs - Aha. I did try that , but only found a solution with the same bytes, so now I'll go back and look for your 2-byte saving... Edit: got it, thanks! Dec 4 '21 at 16:17

# 05AB1E, 25 bytes

[N.µxtExNNn-+N·%>½}¾¹@i,q


Try it here!

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!

• Welcome to Code Golf, and nice answer! Dec 4 '21 at 19:11

# Charcoal, 45 bytes

Ｎθ≔⁰ηＷ‹№υηθ«≦⊕η≔⟦⟧υＦη«≔⁰ζＷ‹ζη«≦⊕κ≧⁺κζ»⊞υζ»»Ｉη


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! 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.

# Rust, 65 64 bytes

|n|{let mut i=1;while(1..=i).filter(|j|i%j<1).count()<n{i+=2};i}


Try it online!

• -1 byte by using <1 instead of ==0 (thanks @Kevin Cruijssen)
• ==0 can be <1. Dec 5 '21 at 18:04

# Python 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!

# Python 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!

• If you're OK with outputting True for 1, you can save 2 bytes with f=lambda n,v=1:n<=sum(v%-~u<1for u in range(v))or 2+f(n,v+2) (TIO).
– xnor
Dec 5 '21 at 10:58

# Wolfram Language (Mathematica), 52 32 bytes

1//.i_/;0~DivisorSigma~i<#:>i+2&


Try it online!

-20 bytes thanks to att! Also thanks to ovs.

Based off alephaleph's excellent insight, and probably not a great Wolfram golf but I couldn't resist those builtins. I'll look forward to att setting me straight.

• 37 bytes by porting alephalpha more literally and Tr[1^...] instead of Length
– ovs
Dec 4 '21 at 7:26
• From there 32 bytes with //. instead of For (Tr[1^Divisors@i], 0~DivisorSigma~i, and DivisorSum[i,1&] are all the same length)
– att
Dec 4 '21 at 7:36
• @att What is //., I can find that documented. I understand ovs's version but a few things in yours lose me... Dec 5 '21 at 22:40
• //. is ReplaceRepeated. It performs replacements until the result stops changing.
– att
Dec 6 '21 at 0:47

# Husk, 14 12 bytes

Fixed a bug and saved 3 bytes thanks to Dominic Van Essen!

ḟo≥⁰S#ȯṁ∫ṫḣN


Try it online!

• I think you're missing an m, like this (the ∫ needs to be mapped across each tail)... Dec 4 '21 at 22:14
• ...but anyway you can get rid of one of the two ⁰ superscripts in the lambda by changing the other one to ¹, like this. Dec 4 '21 at 22:16
• @DominicvanEssen Thanks, I didn't notice that!
– user
Dec 4 '21 at 22:25
• ...You can also save 1 byte using # as count instead of countf, and then save another using S instead of creating a lambda... Dec 4 '21 at 22:27
• @DominicvanEssen Thanks again! The S one takes a while to infer, interesting...
– user
Dec 4 '21 at 22:30

# Ruby, 66 bytes

->n,*r{w=[];1.step.find{|x|w+=r=[0,*r].map{|y|y+x};w.count(x)>=n}}


Try it online!

# Japt, 11 bytes

@>Xâ Ê*Xu}f


Try it

# 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. Output is stored in Ans and displayed.

# 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.

# 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;}


Try it online.

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


# 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!

## 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
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>>