login
Triangle read by rows: T(n,k) is the state of the k-th light after n steps of the light switch problem, 1 <= k <= A003418(n).
2

%I #36 Jun 19 2023 22:36:05

%S 1,1,0,1,0,0,0,1,1,1,0,0,1,1,1,1,1,0,0,1,0,1,0,0,1,0,1,1,1,0,1,1,0,1,

%T 0,1,1,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,0,0,0,1,1,1,1,1,0,1,

%U 0,1,1,0,1,1,1,0,1,0,0,1,1

%N Triangle read by rows: T(n,k) is the state of the k-th light after n steps of the light switch problem, 1 <= k <= A003418(n).

%C The light switch problem posits an infinite number of ordinally numbered lights which are initially off.

%C The 1st step turns all lights on.

%C The 2nd step turns every second one off leaving only odd lights illuminated.

%C The 3rd step reverses the state of every light having a number divisible by 3.

%C Every n-th step thereafter reverses the state of lights with numbers divisible by n.

%C The problem asks which lights are on as n is allowed to be arbitrarily large and the solution is all n where d(n) (A000005) is odd, i.e., the squares A000290. Alternatively, if 0 represents a light that is off and 1 a light that is on, the solution is represented by A010052 with offset 1.

%C This sequence considers intermediate solutions to arrive at A010052. After the n-th step, the lights will have a pattern which must repeats at most every LCM of {1..n} (sequence A003418). This sequence is an irregular triangle read by rows of the n-th repeating sequence.

%H This is illustrated from 2:10 in <a href="https://www.youtube.com/watch?v=-UBDRX6bk-A">The Light Switch Problem Numberphile video</a>

%F T(n,k) = (Sum_{d|k, d<=n} 1) mod 2.

%F T(n,k) = A138553(n,k) mod 2.

%F T(n,k) = A010052(k) for n >= k.

%e Triangle begins:

%e 1;

%e 1,0;

%e 1,0,0,0,1,1;

%e 1,0,0,1,1,1,1,1,0,0,1,0;

%e 1,0,0,1,0,1,1,1,0,1,1,0,1,0,1,1,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,0,0,0,1,1,1,1,1,0,1,0,1,1,0,1,1,1,0,1,0,0,1,1;

%o (PARI) row(n)=my(m=lcm([1..n])); sum(k=1, n, vector(m,i,i%k==0))%2 \\ _Andrew Howroyd_, May 20 2023

%Y Row lengths are A003418.

%Y Cf. A000290, A010052, A138553, A360872.

%K nonn,tabf

%O 1

%A _Andrew Hardy_, Feb 24 2023