A360845 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).

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

Offset

1

Comments

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

The 1st step turns all lights on.

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

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

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

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.

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.

Links

Table of n, a(n) for n=1..81.

This is illustrated from 2:10 in The Light Switch Problem Numberphile video

Formula

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

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

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

Example

Triangle begins:
  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,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;

Prog

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

Crossrefs

Row lengths are A003418.

Cf. A000290, A010052, A138553, A360872.

Sequence in context: A356163 A295895 A179416 * A155972 A010054 A106459

Adjacent sequences: A360842 A360843 A360844 * A360846 A360847 A360848

Keyword

nonn,tabf

Author

Andrew Hardy, Feb 24 2023

Status

approved