AoCG2021 Day 4: Infinite Elves and infinite houses 2

Question

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

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.

Answer 2

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

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.

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

Try it online!

Answer 3

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?

Answer 4

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.

Answer 5

Husk, 10 9 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.

Answer 6

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!

Answer 7

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.

Answer 8

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)

Answer 9

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!

Answer 10

Wolfram Language (Mathematica), ⁵² 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.

Answer 11

Husk, 14 12 bytes

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

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

Try it online!

Answer 12

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!

Answer 13

Japt, 11 bytes

@>Xâ Ê*Xu}f

Try it

Port of @alephalpha answer.

Answer 14

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.

Answer 15

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.

Answer 16

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.

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

Answer 17

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