9
\$\begingroup\$

This challenge (and test cases) are inspired by the work of Project Euler users amagri, Cees.Duivenvoorde, and oozk, and Project Euler Problem 751. (And no, this isn't on OEIS). Sandbox

A non-decreasing sequence of integers \$a_n\$ can be generated from any positive real value \$\theta\$ by the following procedure:

$$ \newcommand{\flr}[1]{\left\lfloor #1 \right\rfloor} \begin{align} b_n & = \begin{cases} \theta, & n = 1 \\ \flr {b_{n-1}} (b_{n-1} - \flr{b_{n-1}} + 1), & n \ge 2 \end{cases} \\ a_n & = \flr{b_n} \end{align} $$

Where \$\flr x\$ is the floor function.

For example, \$\theta=2.956938891377988...\$ generates the Fibonacci sequence: 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

The concatenation of a sequence of positive integers \$a_n\$ is a real value denoted \$τ\$ constructed by concatenating the elements of the sequence after the decimal point, starting at \$a_1\$: $$\tau = a_1.a_2a_3a_4...$$

For example, the Fibonacci sequence constructed from \$\theta=2.956938891377988...\$ yields the concatenation \$τ=2.3581321345589...\$ Clearly, \$τ ≠ \theta\$ for this value of \$\theta\$.

We call a positive real number \$\theta\$ coincidental if \$\theta = τ\$ as generated above.

Challenge

Given a natural number \$k > 0\$ as input, you must output the number of coincidental numbers \$\theta\$ such that \$k = \flr \theta\$.

Test Cases

1   -> 1
2   -> 1
3   -> 0
4   -> 2
5   -> 1
6   -> 0
7   -> 0
8   -> 0
9   -> 0
10  -> 1
11  -> 1
12  -> 1
13  -> 1
14  -> 1
15  -> 1
16  -> 2
17  -> 1
18  -> 1
19  -> 1
20  -> 2
21  -> 2
22  -> 1
23  -> 1
24  -> 1
25  -> 1
26  -> 1
27  -> 2
28  -> 2
29  -> 1
30  -> 2
31  -> 2
32  -> 1
33  -> 0
34  -> 1
35  -> 1
36  -> 3
37  -> 0
38  -> 2
39  -> 3
40  -> 1
41  -> 1
42  -> 1
43  -> 4
44  -> 3
45  -> 1
46  -> 1
47  -> 2
48  -> 2
49  -> 4
50  -> 1
\$\endgroup\$
2
  • \$\begingroup\$ Ok. Sorry, I used to be a whiz at all things math, but that has been more than 20 years ago. It's all those danged ecommerce sites, I tell ya. I got into software to solve puzzles, not to building shopping carts.:) Seriously, though, thank you. I am deleting my first question now out of respect and to keep the playing field clean. I will delete this as well in a bit. Happy coding. \$\endgroup\$
    – Nate T
    Nov 8 '21 at 22:38
  • 1
    \$\begingroup\$ Seriously, brute force cannot be the only solution to this. There has to be some pattern or rule here to build the numbers and I will find it dammit. I think I'm getting close too. Great puzzle btw. Love this sort of stuff. \$\endgroup\$
    – R. Kap
    Nov 12 '21 at 7:42
3
\$\begingroup\$

05AB1E, 33 bytes

žhтã'.ì«ʒтsλ£Dï©->®*}ïć'.«šJyÅ?}g

Brute-force, so extremely slow. The program above validates all real values \$\theta\$ in the range \$[input,input+1)\$ in increments of \$10^{-100}\$. Replacing the two т above with 4 and 5 respectively (to make the increments of size \$10^{-4}\$) at least gives outputs, although does still fail for some of the test cases unfortunately:
Try it online.

: the failing test cases when we use 4 & 5 are: \$k=21\$ (requires at least 9 & 6); \$k=29\$ (requires at least 5 & 4); \$k=33\$ (requires at least 5 & 4); \$k=36\$ (requires at least 6 & 4); \$k=37\$ (requires at least 5 & 4); \$k=39\$ (requires at least 5 & 4); \$k=40\$ (requires at least 5 & 4); \$k=43\$ (requires at least 7 & 5); \$k=44\$ (requires at least 5 & 4); and \$k=49\$ (requires at least 5 & 4).

Explanation:

žh                     # Push builtin 0123456789
  тã                   # Cartesian power of 100: create all possible strings of size 100
                       # using these digits
    '.ì               '# Prepend a "." in front of each
       «               # Merge each to the (implicit) input-integer
                       # (we now have a list of decimal values in the range
                       # [input,input+1) in increments of 1e-100)
        ʒ              # Filter this list of real values `θ` by:
           λ           #  Start a recursive environment,
         т  £          #  to output the first 100 values
          s            #  Where a(0)=`θ`
                       #  and where every following a(n) is calculated as follows:
                       #   (Implicitly push a(n-1))
             D         #   Duplicate this a(n-1)
              ï        #   Floor it
               ©       #   Store this floored a(n-1) in variable `®` (without popping)
                -      #   Subtract it from a(n-1)
                 >     #   Increase it by 1
                  ®*   #   Multiply it by `®`
           }ï          #  After the recursive method: floor all values in the list
             ć         #  Extract the head (the floored value we started with; a.k.a. the
                       #  input); pop and push remainder-list and first item separated to
                       #  the stack
              '.«     '#  Append a "."
                 š     #  Prepend it back to the list
                  J    #  Join this list together to a string
                   yÅ? #  Check if it starts with the current `θ` as prefix
        }g             # After the filter: pop and push the length
                       # (which is output implicitly as result)
\$\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.