What kind of Fibonacci subword at this offset?

Question

When in the Fibonacci number recurrence f_n+2=f_n+f_n+1 one replaces the "+" with string concatenation one will get the sequence of Fibonacci words. If we start with F₀=a and F₁=b, then the first few elements will be a,b,ab,bab,abbab,bababbab,abbabbababbab,... etc.

If N>1 and n<N then F_n will naturally occur as a substring in F_N:

For example, if n=3 and N=6, Then F₄, by construction, contains a copy of F₃ at its end. F₅, being the concatenation of F₃ and F₄, therefore contains two copies, and F₆ three copies, one from F₄ and two from F₅. We can find these copies at offsets 2,5 and 10:

a
b
ab
bab
-->
abbab
 -->
bababbab
--> -->
abbabbababbab
 -->--> -->

But, we cannot rule out more occurrences, for example, there is one at offset 7 that is not directly explained by the recursion formula:

abbabbababbab
 *** 

We'll call such occurrences "strange" as opposed to the "regular" occurrences above.

Task:

Given N>n and offset o your program or function must return one out of three consistent values indicating whether F_n occurs in F_N at offset o and if so which kind of occurrence it is.

Test cases:

N n o answer
------------------------------------------
4 0 0 regular
4 0 1 wrong
4 0 2 wrong
4 0 3 regular
4 0 4 wrong
5 0 0 wrong
5 0 1 regular
5 0 2 wrong
5 0 3 regular
5 0 4 wrong
5 0 5 wrong
5 0 6 regular
5 0 7 wrong
4 1 0 wrong
4 1 1 regular
4 1 2 regular
4 1 3 wrong
4 1 4 regular
5 1 0 regular
5 1 1 wrong
5 1 2 regular
5 1 3 wrong
5 1 4 regular
5 1 5 regular
5 1 6 wrong
5 1 7 regular
1 0 0 wrong
10 2 7 wrong
7 3 0 regular
7 3 7 strange
7 3 9 wrong
7 3 10 regular
7 3 11 wrong
14 7 47 strange
14 7 479 strange
14 7 335 strange
14 7 335 strange
14 7 369 strange
14 7 513 strange
14 7 100 wrong
14 7 200 wrong
14 7 300 wrong
14 7 13 regular
14 7 123 regular
14 7 233 regular
14 7 322 regular

If you need even more test cases here is the Python script that generated the above.

Inspired by this puzzling SE post:

https://puzzling.stackexchange.com/q/122866/71595

• Arnauld: Suggested edge case: 2 0 0 (or anything else with \$n=0\$).
• Arnauld: (\$n=1\$ may also be problematic)
• Albert.Lang: @Arnauld Eugh, give me a moment to fix my reference code.

Answer 1

JavaScript (ES6), 113 bytes

Expects (N)(n)(o) and returns false for strange, true for regular, 2 for wrong.

N=>n=>g=(o,x,y=(U="toUpperCase")[+!x])=>~N--?g(o,n--?y:y=p=y[U](),x&&x+y):(s=x.substr(o,p.length))[U]()==p?s==p:2

Try it online!

Method

We recursively build all patterns \$F_0\$ to \$F_N\$ using letters in lower case (ironically using the 'o' and 't' from the string 'toUpperCase' for golfing reasons).

When \$F_n\$ is reached, we convert it to upper case, save it in \$p\$ and use the transformed string for the recursion. All subsequent regular occurrences of \$p\$ will therefore appear in upper case as well.

At the end of the process, we look for \$p\$ at offset \$o\$ in \$F_N\$:

• If \$p\$ appears in upper case, this is a regular match.
• If \$p\$ appears in lower or mixed case, this is a strange match.
• If \$p\$ doesn't appear at all, this is obviously wrong.

Commented

N => n => // outer functions taking N and n
g = ( // inner recursive function taking:
 o, // the offset o
 x, // a string x (initially undefined)
 y = ( // a string y initialized by using the
 U = "toUpperCase" // first 2 characters of "toUpperCase":
 )[+!x] // - "o" if x is undefined (1st iteration)
 // - "t" if x is defined (2nd iteration)
) => //
~N-- ? // if N != -1 (decrement afterwards):
 g( // do a recursive call:
 o, // pass o unchanged
 n-- ? // if n != 0 (decrement afterwards):
 y // use y unchanged
 : // else:
 y = p = y[U](), // update y and p to y in upper case
 x && x + y // if x is defined, pass x + y
 // (pass undefined otherwise)
 ) // end of recursive call
: // else:
 ( //
 s = x.substr( // s = relevant slice of x
 o, p.length // at offset o and of size p.length
 ) //
 )[U]() == p ? // if s in upper case is equal to p:
 s == p // compare s with p (Boolean value)
 : // else:
 2 // return 2 for 'wrong'

Answer 2

05AB1E, 30 bytes

1ÝλN1›i‚»ë«]1I‚è`IF¦¶Û}Dþ‚sδÅ?

Inputs in the order \$n,N,o\$. Outputs [1,1] for regular; [0,1] for strange; and [0,0] for wrong.

Try it online or verify all test cases.

Explanation:

 λ # Create a recursive environment,
 # to output the infinite sequence
1Ý # Starting with a(0)=0 and a(1)=1
 # Where every following a(x) is calculated as:
 # (implicitly push the previous terms a(x-2) and a(x-1))
 N1›i # If x is larger than first input `n`:
 ‚ # Pair the two previous terms: [a(x-2),a(x-1)]
 » # Join this pair with newline-delimiter
 ë # Else:
 « # Append term a(x-1) to a(x-2) instead
 ] # Close both the if-statement and recursive environment
 1I‚ # Push a pair of the first two inputs: [n,N]
 è # (0-based) index those into the infinite list
` # Pop and push both separated to the stack
 IF # Loop the third input `o` amount of times:
 ¦ # Remove the first bit
 ¶Û # And also trim a potential leading newline character
 }D # After the loop: duplicate the off-set result
 þ # Remove all newlines from the copy, by only keeping digits
 ‚ # Pair the two together
 δ # Map over this pair:
 s Å? # Check for both whether it starts with the n'th term
 # (after which this pair is output implicitly as result)

• Arnauld: FYI, I've fixed my code for \$n<2\$ at the cost of +6 bytes.
• Kevin Cruijssen: @Arnauld Thanks for the heads up, but with the way my recursive method is build up, a straight-forward fix seems to be 8 bytes (¹„abD²èu©²ǝSλè«N²Qiu©]³.$Du‚®δÅ?). Can probably be golfed a bit to 6-7, but that would still tie it with my current approach, so I'll just leave it as is.
• Neil: Feels weird to see an IF in 05AB1E...

Answer 3

Charcoal, 75 bytes

NθNηNζFa×ばつNo...§υ⊕−θηι§υλL§υ−η¬λζ

Try it online! Link is to verbose version of code. Outputs 0 for wrong, 1 for strange and 2 for regular. Explanation:

NθNηNζ

Input N, n and o.

Fab⊞υιFθ⊞υ⭆2§υ−λ2

Generate the first N+2 Fibonacci words.

I∧No⌕A§υθ§υηζ

If o is not one of the places where the nth word appears in the Nth word, then the output is 0.

⊕∨‹η2

If n<2 then the output is 2.

×ばつNo...§υ⊕−θηι§υλL§υ−η¬λζ

Otherwise, the Nth word is composed of copies of the n-1th and nth words, given by the N-n+1th word, where an a in that word represents a copy of the n-1th word and a b in that word represents a copy of the nth word. Using the lengths of the n-1th and nth words, generate the offsets inside the Nth word corresponding to all of the bs which represent all of the regular nth subwords, and check whether o is one of those.

Answer 4

JavaScript (Node.js), 99 bytes

(N,n,o)=>[0,n].map(k=>(F=n=>('ab'[n]||F(n-2)+F(n-1)).replace(/./,n-k&&'$&'))(N).indexOf(F(n),o)==o)

Try it online!

Output [true,true] for regular, [true,false] for strange, [false,false] for wrong.

---

Let's denote \$x\#y\$ as string concatenation, and \$x\left[1:\right]\$ as string slicing which remove the first letter from \$x\$.

$$ F(x)=\begin{cases} \textbf{a}&x=0\\ \textbf{b}&x=1\\ F(x-2)\#F(x-1)&x>1 \end{cases} $$

$$ G(x)=\begin{cases} F(x)&x\le 1\wedge x\ne n\\ G(x-2)\#G(x-1)&x>1\wedge x\ne n\\ \textbf{c}\#F(x)\left[1:\right]&x=n \end{cases} $$

• Define \$F(x)\$ as described in this question, Build \$F(N)\$ and \$F(n)\$ to verify if \$F(n)\$ matches \$F(N)\$ at position \$o\$.
• Define \$G(x)\$, it replace first letter of \$F(n)\$ by a third letter, while keeping other rules of \$F\$. Build \$G(N)\$ and \$G(n)\$ to verify if \$G(n)\$ matches \$G(N)\$ at position \$o\$.
• We collect above 2 values as an array and return it.

I have no idea how to prove its correctness, it simply passed all testcases. Any prove or bad cases are welcomed.

• Albert.Lang: That's fairly similar to my reference implementation. I'd argue that it's correct in principle is kind of obvious, no?

Answer 5

Python3, 356 bytes

I=lambda a:isinstance(a,str)
T=lambda a:a if I(a)else''.join(T(b)for _,b in a)
def O(t,n,C):
 if I(t):return
 for a,b in t:
 if a==n:yield C[0]
 if I(b):C[0]+=len(b)
 else:yield from O(b,n,C)
def f(N,n,o):
 k=[(0,'a'),(t:=1,'b')]
 while(t:=t+1)<=N:k+=[(t,k[-2:])]
 K=dict(k)
 if o in[*O(K[N],n,[0])]:return 2
 if T(K[N])[o:].startswith(T(K[n])):return 1

Try it online!

Answer 6

Wolfram Language(Mathematica), 560 bytes

560 bytes, it can be golfed more.

---

Golfed version. Try it online!

S[a_]:=If[StringQ[a],a,StringJoin[S[Last[#]]&/@a]]
P[a_,b_]:=Flatten[F[a,b,0]]
F[a_,b_,c_]:=Module[{r={},d=c},If[StringQ[a],Return[{}]];Do[With[{i=e[[1]],v=e[[2]]},If[i==b,AppendTo[r,d]];If[StringQ[v],d+=StringLength[v],Module[{s=F[v,b,d]},r=Join[r,s];d+=StringLength[S[v]]]]],{e,a}];r]
B[a_]:=Module[{b={{0,"a"},{1,"b"}},c=1},While[c+1<=a,c++;AppendTo[b,{c,Take[b,-2]}]];b]
H[a_,b_,c_]:=Module[{d,e,f,g,h},d=B[a];e=Association[Rule@@@d];f=P[e[a],b];If[MemberQ[f,c],Return[2]];g=S[e[a]];h=S[e[b]];If[StringLength[g]>c&&StringStartsQ[StringDrop[g,c],h],1,Null]]

Ungolfed version. Try it online!

(* Helper function to check if a value is a string *)
isStringQ[value_] := StringQ[value]
(* Recursively flatten a nested structure to a string *)
flattenToString[structure_] := 
 If[isStringQ[structure], 
 structure,
 StringJoin[flattenToString[Last[#]] & /@ structure]
 ]
(* Find all positions where targetIndex appears in the structure *)
(* Returns a list of positions in the flattened string *)
findPositions[structure_, targetIndex_] := 
 Module[{},
 Flatten[findPositionsHelper[structure, targetIndex, 0]]
 ]
findPositionsHelper[structure_, targetIndex_, currentPos_] := 
 Module[{results = {}, pos = currentPos},
 If[isStringQ[structure], 
 Return[{}] (* No positions found in a string *)
 ];
 
 (* Process each element in the structure *)
 Do[
 With[{index = element[[1]], content = element[[2]]},
 (* If this element's index matches our target, record the current position *)
 If[index == targetIndex, 
 AppendTo[results, pos]
 ];
 
 (* Move position forward based on the content *)
 If[isStringQ[content],
 (* If content is a string, advance position by its length *)
 pos += StringLength[content],
 (* If content is a structure, recursively find positions and advance *)
 Module[{subResults = findPositionsHelper[content, targetIndex, pos]},
 results = Join[results, subResults];
 (* Advance position by the total length of the flattened subcontent *)
 pos += StringLength[flattenToString[content]];
 ]
 ]
 ],
 {element, structure}
 ];
 
 results
 ]
(* Build Fibonacci-like sequence structure *)
buildFibonacciStructure[n_] := 
 Module[{sequence, currentIndex},
 sequence = {{0, "a"}, {1, "b"}};
 currentIndex = 1;
 
 While[currentIndex + 1 <= n,
 currentIndex++;
 AppendTo[sequence, {currentIndex, Take[sequence, -2]}]
 ];
 
 sequence
 ]
(* Main function to check Fibonacci pattern *)
checkFibonacciPattern[N_, n_, offset_] := 
 Module[{fibonacciSequence, fibonacciAssociation, positionsOfN, flattenedN, flattenedN2},
 (* Build Fibonacci-like sequence structure *)
 fibonacciSequence = buildFibonacciStructure[N];
 fibonacciAssociation = Association[Rule @@@ fibonacciSequence];
 
 (* Check if offset matches any position where target index n appears in structure N *)
 positionsOfN = findPositions[fibonacciAssociation[N], n];
 
 If[MemberQ[positionsOfN, offset],
 Return[2] (* regular pattern *)
 ];
 
 (* Check if the flattened string from N starting at offset begins with flattened string of n *)
 flattenedN = flattenToString[fibonacciAssociation[N]];
 flattenedN2 = flattenToString[fibonacciAssociation[n]];
 
 If[StringLength[flattenedN] > offset && 
 StringStartsQ[StringDrop[flattenedN, offset], flattenedN2],
 Return[1], (* strange pattern *)
 Return[Null] (* wrong pattern *)
 ]
 ]
(* Test data *)
testCases = {
 {4, 0, 0, "regular"},
 {4, 0, 1, "wrong"},
 {4, 0, 2, "wrong"},
 {4, 0, 3, "regular"},
 {4, 0, 4, "wrong"},
 {5, 0, 0, "wrong"},
 {5, 0, 1, "regular"},
 {5, 0, 2, "wrong"},
 {5, 0, 3, "regular"},
 {5, 0, 4, "wrong"},
 {5, 0, 5, "wrong"},
 {5, 0, 6, "regular"},
 {5, 0, 7, "wrong"},
 {4, 1, 0, "wrong"},
 {4, 1, 1, "regular"},
 {4, 1, 2, "regular"},
 {4, 1, 3, "wrong"},
 {4, 1, 4, "regular"},
 {5, 1, 0, "regular"},
 {5, 1, 1, "wrong"},
 {5, 1, 2, "regular"},
 {5, 1, 3, "wrong"},
 {5, 1, 4, "regular"},
 {5, 1, 5, "regular"},
 {5, 1, 6, "wrong"},
 {5, 1, 7, "regular"},
 {1, 0, 0, "wrong"},
 {10, 2, 7, "wrong"},
 {7, 3, 0, "regular"},
 {7, 3, 7, "strange"},
 {7, 3, 9, "wrong"},
 {7, 3, 10, "regular"},
 {7, 3, 11, "wrong"},
 {14, 7, 47, "strange"},
 {14, 7, 479, "strange"},
 {14, 7, 335, "strange"},
 {14, 7, 335, "strange"},
 {14, 7, 369, "strange"},
 {14, 7, 513, "strange"},
 {14, 7, 100, "wrong"},
 {14, 7, 200, "wrong"},
 {14, 7, 300, "wrong"},
 {14, 7, 13, "regular"},
 {14, 7, 123, "regular"},
 {14, 7, 233, "regular"},
 {14, 7, 322, "regular"}
};
(* Expected result mapping *)
expectedResults = <|
 "regular" -> 2,
 "strange" -> 1,
 "wrong" -> Null
|>;
(* Run tests *)
Print["\n=== RUNNING TESTS ==="];
testResults = Table[
 With[{N = testCase[[1]], n = testCase[[2]], offset = testCase[[3]], expected = testCase[[4]]},
 Module[{result = checkFibonacciPattern[N, n, offset]},
 {
 testCase,
 result,
 expectedResults[expected],
 result === expectedResults[expected]
 }
 ]
 ],
 {testCase, testCases}
];
(* Check if all tests passed *)
allTestsPassed = AllTrue[testResults, Last];
If[allTestsPassed,
 Print["All tests passed!"],
 Print["Some tests failed:"];
 failedTests = Select[testResults, Not[Last[#]] &];
 Print["Number of failed tests: ", Length[failedTests]];
 Print["First few failed tests:"];
 Take[failedTests, Min[5, Length[failedTests]]] // TableForm // Print
];