generating perfect powers using locker operations

Question

Suppose there are n lockers that're all initially closed. For which positive integers $k\leq 10$ can one find a sequence of operations $T_{i_1},\cdots, T_{i_j}$, where each operation $T_i$ changes some lockers by toggling all multiples of $i$, so that at the end of the operations, all lockers that remain open are precisely those that are $k$th powers (and at most n)?

Clarification: the original question was trivial, asking if one could pick which lockers were toggled. The idea was to generalize the result for the perfect square case.

Obviously $k=1,2$ work. But I'm not sure about $k=3$. I know that each prime factor of a perfect cube has an exponent that's a multiple of 3. I also know some variants of this problem (e.g. to generate perfect squares, have $T_k$ toggle all lockers that're multiples of $k$, to generate all numbers that are twice a perfect square, have $T_k$ toggle all lockers that're multiples of $2k$, and to generate all numbers that are of the form $an^2$ for any integer a, just let $T_k$ toggle all multiples of $ak$). So as a specific example, if $n=9,$ I'd only want to keep lockers $1,8$ open, meaning that they're toggled an odd number of times.

Answer 1

This is always possible for any set of numbers. I’m assuming that $T_k$ flips multiples of $k$ and we can choose some subset of all such operations to actually run.

Let’s do induction - it’s trivial to correctly satisfy everything in the empty set ($n=0$). Let’s say we’ve toggled some subset of $T_1,…,T_{n-1}$ to correctly set everything less than $n$. This will leave the $n$th locker in some state. Note that $T_n$ toggles $n$ and nothing less than $n$, so we can use it (or not) to correctly set the $n$th locker without touching anything lower. This gives us the desired solution for setting the first $n$ lockers.

Let's derive the exact relationship between the set of open lockers (call it $S$) and the set of toggled operations (call it $R$).

We know that $s\in S$ iff the number of divisors of $s$ which get all there multiples toggled is odd. In mathematical language using indicator functions: $1_S(s) \equiv \sum_{m|s} 1_R(M) \mod 2$

The Mobius Inversion formula (https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula) gives the inverse of the above formula when $S$ is a multiplicative set (meaning that if $a,b\in S$ then $ab\in S$). Simplifying it (the original formula uses the Mobius function which is -1,0, or 1, but can be simplified mod 2) gives that $T_m$ is used iff $\sum_{a| m, a\text{ squarefree}}1_S(m/a)$ is even.

For powers of order $k$, this simplifies to the following: for $n=\prod p_i^{e_i}$, $T_n$ is used iff for all $i$, $e_i\mod k$ is 0 or 1.

Answer 2

This is building on the approach by @Eric. Let $T_k$ be the action that toggles all multiples of $k$. We consider any (finite or infinite) sequence of toggles where each later toggle must have a higher $k$ than any earlier toggle. It is well known that:

• The finite sequence $(T_1)$ leaves all doors open.

• The infinite sequence $(T_1, T_2, T_3, \dots)$, i.e. every toggle is performed, leaves only perfect squares open.

I wrote some code to see what toggles would have to be skipped to achieve 3rd powers (perfect cubes), 4th powers, etc. Here are the results, but I have not discerned any pattern yet. Hopefully others will find this useful?

For cubes, these toggles are skipped, i.e. the toggles performed are $(T_1, T_2, T_3, T_5, T_6, T_7, T_8, T_{10}, \dots)$:

4, 9, 12, 18, 20, 25, 28, 32, 36, 44, 45, 49, 50, 52, 60, 63, 68, 72, 
75, 76, 84, 90, 92, 96, 98, 99, 100, 108, 116, 117, 121, 124, 126, 132, 
140, 144, 147, 148, 150, 153, 156, 160, 164, 169, 171, 172, 175, 180, 
188, 196, 198, 200, 204, 207, 212, 220, 224, 225, 228, 234, 236, 242, 
243, 244, 245, 252, 256, 260, 261, 268, 275, 276, 279, 284, 288, 289, 
292, 294, 300, 306, 308, 315, 316, 324, 325, 332, 333, 338, 340, 342, ...

For 4th-powers, these toggles are skipped:

4, 8, 9, 12, 18, 20, 24, 25, 27, 28, 36, 40, 44, 45, 49, 50, 52, 54, 
56, 60, 63, 64, 68, 72, 75, 76, 84, 88, 90, 92, 98, 99, 100, 104, 108, 
116, 117, 120, 121, 124, 125, 126, 128, 132, 135, 136, 140, 144, 147, 
148, 150, 152, 153, 156, 164, 168, 169, 171, 172, 175, 180, 184, 188, 
189, 192, 196, 198, 200, 204, 207, 212, 216, 220, 225, 228, 232, 234, 
236, 242, 244, 245, 248, 250, 252, ...

And my code:

import numpy as np

# arr[0...n-1] of size n
# arr[j] represents integer j+1

# toggle the integers k, 2k, 3k, 4k, ...
def toggle(arr, n, k):
  for j in range(k-1, n, k):
    arr[j] = 1- arr[j]

# performs toggles to leave ON all pth-powers up to n
def main(n, p):
  arr = np.zeros(n, dtype=int) # initially all off
  skips = []
  root = 1 # root of the next pth-power
  for j in range(n):
    i = j+1
    if (i == pow(root, p)):
      root += 1
      # want perfect power i to be ON, so toggle if it's off
      tog = (arr[j] == 0)
    else:
      # want i to be OFF, so toggle if it's on
      tog = (arr[j] == 1)
    if tog:
      toggle(arr, n, i)
    else:
      skips.append(i)

  nums = []
  for j in range(n):
    if arr[j] == 1:
      nums.append(j+1)
  print(nums) # sanity check to verify only pth-powers are on
  print(skips)