cp's OEIS Frontend

A293865 Number of self-intersecting walks of length n on a square lattice such that at each point the angle turns 90 degrees.

%I A293865 #26 Oct 30 2017 22:59:41
%S A293865 0,0,0,1,1,2,3,5,8,13,21,37,56,90,144,239,374,592,948,1558,2431,3848,
%T A293865 6127,9972,15602,24658,39158,63265,99110,156505,248040,398675,625024,
%U A293865 986241,1560763,2498832,3919561,6180914,9770162,15594972,24470070,38567903,60907330
%N A293865 Number of self-intersecting walks of length n on a square lattice such that at each point the angle turns 90 degrees.
%C A293865 It is assumed that the first walk turns left and that all walks end when they intersect themselves.
%H A293865 MathStackExchange, <a href="https://math.stackexchange.com/questions/2471391/expected-number-of-steps-before-intersection">Expected Number of Steps Before Intersection</a>, Oct 2017.
%F A293865 For n>2, a(n) = 2*A189722(n-1) - A189722(n). - _Jens Randrup Rasmussen_, Oct 29 2017
%e A293865 For n = 4 we have the simplest self-intersecting walk, which is a square.
%e A293865 For n = 5 we have the walk:
%e A293865 (0,0), (0,1), (-1,1), (-1, 2), (0,2), (0,1)
%e A293865 For n = 6 we have the walks:
%e A293865 (0,0), (0,1), (-1,1), (-1, 0), (-2,0), (-2,1), (-1,1)
%e A293865 (0,0), (0,1), (-1,1), (-1, 2), (-2,2), (-2,1), (-1,1)
%o A293865 (Visual Basic for Excel)
%o A293865 Const N = 50
%o A293865 Const MaxSteps = 43
%o A293865 Dim BeenHere() As Boolean
%o A293865 Dim LoopBacks(MaxSteps) As Long
%o A293865 Dim PosX As Integer, PosY As Integer
%o A293865 Sub Macro1()
%o A293865   ReDim BeenHere(N, N)
%o A293865   PosX = N / 2: PosY = N / 2
%o A293865   BeenHere(PosX, PosY) = True
%o A293865   PosX = PosX + 1
%o A293865   BeenHere(PosX, PosY) = True
%o A293865   PosY = PosY - 1
%o A293865   BeenHere(PosX, PosY) = True
%o A293865   DoSteps 2, 3, PosX, PosY, BeenHere()
%o A293865   For i = 4 To MaxSteps
%o A293865     Cells(i - 1, 3).Value = i
%o A293865     Cells(i - 1, 4).Value = LoopBacks(i)
%o A293865   Next i
%o A293865 End Sub
%o A293865 Sub DoSteps(ByVal StepNo As Integer, Dir As Integer, X As Integer, Y As Integer, BH() As Boolean)
%o A293865 Dim BH2() As Boolean
%o A293865 Dim X1 As Integer, Y1 As Integer, X2 As Integer, Y2 As Integer
%o A293865 Dim Dir1 As Integer, Dir2 As Integer
%o A293865   BH2 = BH
%o A293865   StepNo = StepNo + 1
%o A293865   Select Case Dir
%o A293865   Case 1, 3 ' North or South
%o A293865       Dir1 = 2: X1 = X + 1: Y1 = Y
%o A293865       Dir2 = 4: X2 = X - 1: Y2 = Y
%o A293865   Case 2, 4 ' East or West
%o A293865       Dir1 = 1: Y1 = Y + 1: X1 = X
%o A293865       Dir2 = 3: Y2 = Y - 1: X2 = X
%o A293865   End Select
%o A293865   If BH2(X1, Y1) Then
%o A293865     LoopBacks(StepNo) = LoopBacks(StepNo) + 1
%o A293865   ElseIf StepNo < MaxSteps Then
%o A293865     BH2(X1, Y1) = True
%o A293865     DoSteps StepNo, Dir1, X1, Y1, BH2()
%o A293865     BH2(X1, Y1) = False
%o A293865   End If
%o A293865   If BH2(X2, Y2) Then
%o A293865     LoopBacks(StepNo) = LoopBacks(StepNo) + 1
%o A293865   ElseIf StepNo < MaxSteps Then
%o A293865     BH2(X2, Y2) = True
%o A293865     DoSteps StepNo, Dir2, X2, Y2, BH2()
%o A293865   End If
%o A293865 End Sub
%Y A293865 This sequence gives the number of self-intersecting walks while A189722 gives the number of self-avoiding walks.
%K A293865 nonn,walk
%O A293865 1,6
%A A293865 _Jens Randrup Rasmussen_, Oct 18 2017
%E A293865 The terms starting from a(11) and the program corrected by _Jens Randrup Rasmussen_, Oct 29 2017