Return to Answer

If we can assert that a ruler has implicit marks of \$0\$ and \$N\$, which I believe is part of the definition of a sparse ruler, then we know that \$N\$ is always in the set of all distances a ruler can measure and hence \$k \ge N\$. At the same time, we cannot hope to measure any distance greater than \$N\$ (as that is the length of our ruler!), so \$k=N\$.

If we can assert that a ruler has implicit marks of \$0\$ and \$N\$, which I believe is part of the definition of a sparse ruler, then we know that \$N\$ is always in the set of all distances a ruler can measure and hence \$k \ge N\$. At the same time, we cannot hope to measure any distance greater than \$N\$ (as that is the length of our ruler!), so \$k=N\$. Furthermore, no ruler of length less than \$N\$ can make as many measurements (they can't measure \$N\$).

‘ŒPŒcIQLƲÐṀLÐṂṬṚ - Link: non-negative integer, N
‘                - increment {N} -> N+1
 ŒP              - powerset {[1..N+1]}
                   -> [[],[1],[2],...,[N+1],[1,2],[1,3],...,[1..N+1]]
                      i.e. all rulers of length <=N where the 0-mark is represented
                           by a value of 1 or higher while no value may exceed N+1
                           (e.g. [1,3,8] & [2,4,9] both represent [0,2,7] when N>=9)
                           Note that there is, therefore, exactly one representation
                           present of every sparse-ruler of length N
         ÐṀ      - keep those maximal under:
        Ʋ        -   last four links as a monad:
   Œc            -     unordered pairs
     I           -     forward deltas
      Q          -     deduplicate
       L         -     length
            ÐṂ   - keep those minimal under:
           L     -   length
              Ṭ  - untruth (convert to their binary representations)
               Ṛ - reverse (equivalent to sorting by binary representation)

‘ŒPŒcIQLƲÐṀLÐṂṬṚ - Link: non-negative integer, N
‘                - increment {N} -> N+1
 ŒP              - powerset {[1..N+1]}
                   -> [[],[1],[2],...,[N+1],[1,2],[1,3],...,[1..N+1]]
                      i.e. all rulers of length <=N where the 0-mark is represented
                           by a value of 1 or higher while no value may exceed N+1
                           (e.g. [1,3,8] & [2,4,9] both represent [0,2,7] when N>=8)
                           Note that there is, therefore, exactly one representation
                           present of every sparse-ruler of length N
         ÐṀ      - keep those maximal under:
        Ʋ        -   last four links as a monad:
   Œc            -     unordered pairs
     I           -     forward deltas
      Q          -     deduplicate
       L         -     length
            ÐṂ   - keep those minimal under:
           L     -   length
              Ṭ  - untruth (convert to their binary representations)
               Ṛ - reverse (equivalent to sorting by binary representation)

‘ŒPŒcIQLƲÐṀLÐṂṬṚ - Link: non-negative integer, N
‘                - increment {N} -> N+1
 ŒP              - powerset {[1..N+1]}
                   -> [[],[1],[2],...,[N+1],[1,2],[1,3],...,[1..N+1]]
                      i.e. all rulers of length <=N where the "0 mark" is allowed to
                           be higher, while no mark may exceed N
                           (e.g. [1,3,8] & [2,4,9] both represent [0,2,7] when N>=9)
         ÐṀ      - keep those maximal under:
        Ʋ        -   last four links as a monad:
   Œc            -     unordered pairs
     I           -     forward deltas
      Q          -     deduplicate
       L         -     length
            ÐṂ   - keep those minimal under:
           L     -   length
              Ṭ  - untruth (convert to their binary representations)
               Ṛ - reverse (equivalent to sorting by binary representation)

‘ŒPŒcIQLƲÐṀLÐṂṬṚ - Link: non-negative integer, N
‘                - increment {N} -> N+1
 ŒP              - powerset {[1..N+1]}
                   -> [[],[1],[2],...,[N+1],[1,2],[1,3],...,[1..N+1]]
                      i.e. all rulers of length <=N where the 0-mark is represented
                           by a value of 1 or higher while no value may exceed N+1
                           (e.g. [1,3,8] & [2,4,9] both represent [0,2,7] when N>=9)
                           Note that there is, therefore, exactly one representation
                           present of every sparse-ruler of length N
         ÐṀ      - keep those maximal under:
        Ʋ        -   last four links as a monad:
   Œc            -     unordered pairs
     I           -     forward deltas
      Q          -     deduplicate
       L         -     length
            ÐṂ   - keep those minimal under:
           L     -   length
              Ṭ  - untruth (convert to their binary representations)
               Ṛ - reverse (equivalent to sorting by binary representation)