16
\$\begingroup\$

Recently a friend of mine posed the following:

What subset of the integers satisfies the condition if distinct a and b are in the subset, their average is not in the subset? I know the set of non-0 squares satisfies the condition, but I wonder if there exists a more... dense set that satisfies the condition.

(It turns out my friend was wrong about "the set of non-0 squares satisfies the condition", just ignore that.)

Now, I thought I could turn this into a coding challenge.

The goal of this challenge is to submit a function \$f: \mathbb{N} \to \{\top, \bot\}\$ which takes in a positive integer and returns a boolean satisfying the conditions in the "Rules" section.

Your score is the length of your program in bytes. Program \$A\$ is better than program \$B\$ if \$A\$ is shorter than \$B\$.

Rules

  • For any distinct \$a, b\$ so that \$f(a)\$ is true, \$f(b)\$ is true and \$a+b\$ is even, then \$f(\frac{a+b}{2})\$ is false.
  • Let \$e: \mathbb{N} \to \mathbb{N}\$ be defined as \$e(x) = \text{the } x^{\text{th}} \text{ number so that } f(x) \text{ is true}\$. Then, there exists some \$m\$ so that \$e(n) < n^2\$ for all \$n \geq m\$.
  • The set \$\{a: f(a) \text{ is true}\}\$ is infinite, i.e. you can't make \$f\$ hold for only finitely many values.

Leaderboard

  1. allxy - 4 bytes (Jelly)
  2. Neil - 6 bytes (Charcoal)
  3. m90 - 10 bytes (x86 32-bit machine code)
  4. m90 - 12 bytes (Re:direction)
  5. Dominic van Essen - 15 bytes (BQN)
  6. knomologs - 20 bytes (МК-52/МК-61)
  7. alephalpha - 22 bytes (PARI/GP)
  8. chunes - 23 bytes (Factor + math.unicode) (tied with #8)
  9. G B - 23 bytes (Ruby) (tied with #7)
  10. Neil - 26 bytes (Retina 0.8.2)
  11. Arnauld - 28 bytes (JavaScript ES6)
  12. loopy walt - 31 bytes (Python 2)
  13. loopy walt - 33 bytes (Python)
  14. solid.py - 50 bytes (Python 3.6)
  15. friddo - 68 bytes (Python 3.8)
  16. Kevin Cruijssen - 110 bytes (Whitespace)
\$\endgroup\$
8
  • 3
    \$\begingroup\$ I assume there is a typo in the second part of the 'Program A is better than program B...' sentence... otherwise, what is 𝑔𝐴(𝑛)? \$\endgroup\$ Apr 7 at 10:26
  • 1
    \$\begingroup\$ I also don't quite understand the purpose of the inequality "𝑓𝐴(𝑛)<𝑔𝐴(𝑛)" - whatever this is supposed to mean, surely if program A is shorter than program B, but it gives exactly the same results (which wouldn't satisfy the inequality), then it should be 'better'...? \$\endgroup\$ Apr 7 at 10:28
  • 4
    \$\begingroup\$ I think this challenge would have greatly benefited from spending some time in the Sandbox. \$\endgroup\$
    – pajonk
    Apr 7 at 10:42
  • 5
    \$\begingroup\$ And: "I know the set of non-0 squares satisfies the condition" - but isn't the average of the squares of 2 (4) and 14 (196) equal to the square of 10 (100)? \$\endgroup\$ Apr 7 at 10:43
  • 5
    \$\begingroup\$ Interesting side fact: the ternary construction that everyone here has implemented is not optimal in terms of density! \$\endgroup\$ Apr 8 at 6:30

15 Answers 15

15
\$\begingroup\$

A simple greedy approach gives the set [1, 2, 4, 5, 10, 11, 13, 14...]. This is probably optimal.

It can be constructed by:

  • Start with the set [1]
  • Forever:
    • Take the maximum value of the set, double it, and subtract 1
    • Add that to each value of the set
    • Append that to the current set

Here's an example program to do this.

After a bit of digging on OEIS, we find that the sequence we're looking for is A003278.

A more convenient way of constructing this set is to use one of the definitions on said OEIS page - Try it Online!

This one takes the infinite list of nonnegative integers, converts each to binary and from ternary, and increments them.

This definition is really easy to implement as a check. We simply check that (n-1) in ternary contains no twos.

The sequence plus or minus any constant has the same properties so we can check if n in ternary contains no twos. Thanks to Jonathan Allan for this insight, saving a byte on both versions.

Finally:

Vyxal, 5 bytes

3τ2<A

Try it Online!

3τ    # Convert to base 3
    A # Are all elements
  2<  # Less than 2?

Jelly has a convenient builtin for this which saves a byte:

Jelly, 4 bytes

b3ỊȦ

Try it online!

b3   # Convert to base 3
   Ȧ # Are all elements
  Ị  # Less than two?
\$\endgroup\$
3
  • \$\begingroup\$ Nice! 5 bytes in Husk, too (also using convienient eps builtin = "Has absolute value at most 1"...). \$\endgroup\$ Apr 7 at 10:19
  • \$\begingroup\$ @DominicvanEssen Yeah, that's exactly the same as Jelly's \$\endgroup\$
    – allxy
    Apr 7 at 10:46
  • \$\begingroup\$ I think oeis.org/A005836 also has the desired properties, so no need to decrement. \$\endgroup\$ Apr 7 at 16:50
4
\$\begingroup\$

Python 2, 27 bytes

f=lambda n:n>n%3/2>-f(n/3) 

Try it online!

Swaps True and False.

Python 2, 29 bytes (@xnor)

f=lambda n:n<1or n%3<2*f(n/3)

Try it online!

Thanks to @Jonathan Allan for convincing me that @xnor's switching to A005836 (without its first element) is actually perfectly good.

Python 2, 31 bytes (@KevinCruijssen)

f=lambda n:n<2or n%3>0<f(n/3+1)

Attempt This Online!

Improved logic is inspired by @alephalpha's PARI/GP answer. Could save another two bytes by allowing any nonzero value for True.

Python, 33 bytes

f=lambda n:n<2or n%3and f(n//3+1)

Attempt This Online!

Uses the base 3 characterisation at OEIS. Returns 0 and True.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ -1 byte by switching to Python 2 so the // can be /. \$\endgroup\$ Apr 7 at 14:09
  • 2
    \$\begingroup\$ @KevinCruijssen 1 byte is below my switching threshold ;-D \$\endgroup\$
    – loopy walt
    Apr 7 at 14:17
  • 1
    \$\begingroup\$ @KevinCruijssen found a second one. \$\endgroup\$
    – loopy walt
    Apr 7 at 15:00
  • 1
    \$\begingroup\$ It looks like it works to do this to check that the number has no 2's in ternary: f=lambda n:n<1or n%3<2*f(n/3) (TIO) \$\endgroup\$
    – xnor
    Apr 7 at 19:39
  • 2
    \$\begingroup\$ The challenge specification just gives the properties required, it does not have to be A003278 itself. oeis.org/A005836 is numbers without any 2s in the ternary representation and is what xnor's code implements, and since it is just the same infinite sequence with all terms being one less it also satisfies the requirements. (it does include 1, although I don't think that is actually a requirement, and 0 is not part of the specified input domain anyway) \$\endgroup\$ Apr 8 at 11:18
3
\$\begingroup\$

Charcoal, 7 6 bytes

›²⌈↨N³

Try it online! Link is to verbose version of code. Outputs - if the input is a member of A005836, nothing if not. Explanation: Another port of @allxy's solution.

 ²      Literal integer `2`
›       Is greater than
  ⌈     Maximum of
    N   Input number
   ↨    Converted to base
     ³  Literal integer `3`
        Implicitly print

Previous 7-byte version:

›2⌈⍘⊖N³

Try it online! Link is to verbose version of code. Outputs - if the input is a member of A003278, nothing if not. Explanation:

 2      Literal characater `2`
›       Is greater than
  ⌈     Maximum of
     N  Input integer
    ⊖   Decremented
   ⍘    Converted to base
      ³ Literal integer `3`
        Implicitly print

String base conversion is used because array base conversion returns an empty array for an input of 1 (decremented) which has no maximum.

A003278 is infinitesimally denser than A005836 because it effectively includes an extra element at the beginning, so given any finite integer, the number of terms in A003278 less than that integer is always at least as many as the number of terms in A005836 less than that integer, but I don't know whether A003278 always beats all other possible subsets in this way.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 25 bytes

A port of loopy walt's answer.

24 bytes if we can return zero / non-zero.

f=n=>n<2||n%3&&f(-~(n/3))

Try it online!

\$\endgroup\$
2
\$\begingroup\$

PARI/GP, 22 bytes

f(n)=n<2||f(n\3+1)*n%3

Attempt This Online!

A port of loopy walt's Python answer.

\$\endgroup\$
2
\$\begingroup\$

Электроника МК-52/МК-61, 20 bytes

X→П0 3 - Fx≥0 18 П→X0 3 ÷ K{x} Fx≠0 19 FBx K[x] 1 + X→П0 БП 01 1 С/П

or, in bytecode:

40 03 11 59 18 60 03 13 35 57 19 0F 34 01 10 40 51 01 01 50

Port of loopyWalt's Python answer.

The MK-52 and MK-61 were the most advanced Soviet programmable calculators to use keystroke programming (later models, like the MK-85 and MK-90, had a form of BASIC). Despite looking more like macros than "real" programs, the language is actually Turing-complete. Each instruction occupies 1 byte in memory. Code-golfing was in fact very popular with these calculators in the 80s, because one had to fit the program in 104 bytes – however, even quite complex games were written with this limitation.

Online emulator here. Turn on the calculator (switch labeled Вкл), paste the above bytecode into the text area on the right and click "Ввести в память" ("Write to memory"). Input number into calculator and press В/О, then С/П to run program. Outputs 1 for true and 0 for false (not exactly quickly though...)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf. This is really cool, nice answer! \$\endgroup\$ Apr 18 at 13:29
2
\$\begingroup\$

Re:direction, 12 bytes

+++>
v +>
 <

Try it online!

Outputs by exit code, 0 for False and 1 (by queue underflow) for True. (This is a bit dubious; it matches the usual convention for numbers in general, but is the opposite of the convention normally used for exit codes.)

The condition used is that the number consists only of 0s and 2s in ternary, which is another variation that also works. This program goes into an infinite loop on 0, which thankfully does not need to be handled.

The following notation will be used for the contents of the queue: a number means that many s, and | means one . If the input number is N, the initial queue is N|.

The possibilities are as shown:

Execution path for 3N Execution path for 3N+1 Execution path for 3N+2

Execution path for 2

\$\endgroup\$
2
\$\begingroup\$

Regex (or Retina), 9 bytes

^[0268]*$

Try it online!

For any two different numbers composed of 0, 2, 6, 8 in decimal, at any digit position where they differ, their average has 1, 3, 4, 5, or 7, and thus does not satisfy the condition.

This condition includes asymptotically \$ 4^{log_{10}n} = n^{log_{10}4} \approx n^{0.602}\$ of the first \$n\$ numbers.

\$\endgroup\$
1
\$\begingroup\$

Python 3.8 (pre-release), 68 bytes

lambda n,s={1}:any(n in(s:=s|{a+max(s)*2-1for a in s})for _ in[0]*n)

Try it online!

By no means the shortest solution, but a fun one!
Builds up the set using the method described by @allxy's Jelly answer and checks if n is in it.

\$\endgroup\$
1
\$\begingroup\$

Retina 0.8.2, 26 bytes

.+
$*
+`^1?(1*)\1\1$
$1
^$

Try it online! Link includes test cases. Outputs 1 if the input is a member of A005836, 0 if not. Explanation:

.+
$*

Convert to unary.

+`

Repeat as many times as possible...

^1?(1*)\1\1$
$1

... integer divide by 3, but only if the remainder is not 2.

^$

Test to see whether it was possible to reach 0.

\$\endgroup\$
1
\$\begingroup\$

Factor + math.unicode, 23 bytes

[ 1 - 3 >base "10"⊂ ]

Try it online!

Based on @allxy's Vyxal/Jelly answers. Subtract 1 from the input, convert it to base 3, but instead of checking whether each digit is less than two, check whether the result is a subset of "10" since that's shorter in Factor.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 23 bytes

->n{(n-1).to_s(3)!~/2/}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Whitespace, 110 bytes

[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve_input][N
S S N
_Create_Label_FUNC][S N
S _Duplicate_input][S S S T S N
_Push_2][T  S S T   _Subtract][N
T   T   T   N
_If_negative_Jump_to_Label_TRUTHY][S N
S _Duplicate_input][S S S T T   N
_Push_3][T  S T T   _Modulo][S S S N
_Push_0][S N
T   _Swap_top_two][T    S S T   _Subtract][N
T   T   S N
_If_negative_Jump_to_label_CONTINUE][N
N
N
_Exit_Program][N
S S S N
_Create_Label_CONTINUE][S S S T T   N
_Push_3][T  S T S _Integer_divide][S S S T  N
_Push_1][T  S S S _Add][N
S N
N
_Jump_to_Label_FUNC][N
S S T   N
_Create_Label_TRUTHY][S S S T   N
_Push_1][T  N
S T _Print_1_as_number]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Port of @loopyWalt's Python answer.

Whitespace doesn't have any booleans, but this will output 1 for truthy and nothing for falsey (could also output 0 for falsey at the cost of 8 additional bytes).

Try it online (with raw spaces, tabs and new-lines only).

Explanation in pseudo-code:

Integer n = STDIN as number
FUNC:
  If(n-2 is negative):
    Jump to TRUTHY
  If(0-(n%3-1) is negative):
    Jump to CONTINUE
  Exit program (falsey result)

CONTINUE:
  n = n//3+1
  Jump to FUNC

TRUTHY:
  Print 1 as number to STDOUT
  (implicitly stop the program with an error stating 'no exit is defined')
\$\endgroup\$
1
\$\begingroup\$

x86 32-bit machine code, 10 bytes

48 25 AA AA AA AA 0F 94 C0 C3

Try it online!

Uses the regparm(1) calling convention – argument in EAX, result in AL.

This implements a slightly different criterion from the one most other answers use: n-1 consists of only 0s and 1s in base 4. This still works, and barely satisfies the \$e(n) < n^2\$ condition; removing the subtraction of 1 would make it fail that condition.

This modified criterion is simple to implement, by checking whether the odd-position bits in n-1 are all zero.

In assembly:

f:
    dec eax
    and eax, 0xAAAAAAAA
    setz al
    ret
\$\endgroup\$
3
  • \$\begingroup\$ I think you've mis-read Rule 2: by subtracting 1, you're satisfying e(n) < n^2 for all n, but you only need to satisfy it for n ≥ some number m. Without dec eax Rule 2 is satisfied with m=9... \$\endgroup\$ Apr 12 at 13:48
  • 1
    \$\begingroup\$ @DominicvanEssen No, that version fails at 16 (e(16) = 256 = 16^2) and again at every power of 2. \$\endgroup\$
    – m90
    Apr 12 at 14:03
  • \$\begingroup\$ Ah, yes, you're right. My mistake: I was staring at a screenfull of numbers & didn't spot that. \$\endgroup\$ Apr 12 at 14:09
1
\$\begingroup\$

BQN, 15 14 13 bytes

Edit: -1 byte thanks to Razetime

⌊´2-3|⊢⌊∘÷3⋆↕

Try it at BQN online REPL

             ↕      # range from 0...input-1
           3⋆       # get 3 to the power of those
        ⌊∘÷         # now use these to divide & floor (=integer division)
       ⊢            # the input
     3|             # get each one modulo 3
   2-               # subtract it from 2
 ⌊´                 # and find the minimum

The final 2>·⌈´ ⌊´2- part seems a bit clunky to me (although now improved a bit): I'd want to be able to do something like ¬2∊ (NOT is 2 a member of), but unfortunately this returns an array which doesn't seem to work as a boolean.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 3⋆¨ is 3⋆ , vectorizes \$\endgroup\$
    – Razetime
    Apr 12 at 14:24
  • \$\begingroup\$ Ah, yes, thanks (again). \$\endgroup\$ Apr 12 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.