Go away! No-1's Here!

Question

I was playing around with some numbers and found a sequence that, of course, is on OEIS. It is A005823: Numbers whose ternary expansion contains no 1's. It goes:

a(2n) = 3*a(n)+2

a(2n+1) = 3*a(n+1)

a(1) = 0

a = 0,2,6,8,18,20,24,26,54....

I wrote a CJam program that generates the first n of these numbers by converting the index to binary, replacing the 1's with 2's, and converting from ternary to decimal.

I also noticed that any even number can be obtained by taking the sum of two numbers in the sequence (sometimes the number with itself).

The Challenge:

Given any non-negative even number as input, output the indices of two numbers in the sequence that sum to it. (Note that sometimes multiple pairs are possible.)

The Rules:

• Specify if you're using 0- or 1-indexing.
• If you're outputting as a string, put a delimiter between the two indices.
• You are allowed to output as a complex number.
• If you so desire, you can output every valid pair.
• Code Golf: shortest answer wins

Test Cases

I use 0-indexing. Here I list every possible output for each input, but you only need to output one.

0:      [0 0]
2:      [1 0]
4:      [1 1]
6:      [2 0]
8:      [2 1]   [3 0]
10:     [3 1]
12:     [2 2]
14:     [3 2]
16:     [3 3]
18:     [4 0]
30:     [6 2]
32:     [6 3]   [7 2]
46:     [7 5]
50:     [7 6]
120:    [10 10]
338:    [19 18]
428:    [30 23] [31 22]
712:    [33 27] [35 25] [41 19] [43 17] [49 11] [51 9]  [57 3]  [59 1]
1016:   [38 37] [39 36]

Thanks to @Luis Mendo for test case help.

Related: Is it within the Cantor set?

Answer 1

Husk, 21 14 13 bytes

-7 bytes, thanks to @Neil's JS answer

-1 byte inspired by betaveros's Parradoc answer

Uses 0-indexing

mḋTmMo±>ḋ2B3½

Try it online!

Explanation

            ½    Half the input
          B3     Convert to Base 3
   m             Map over the list
    Mo±>ḋ2       Function such that: 0 -> [0,0], 1 -> [0,1], 2 -> [1,1]
        ḋ2       Binary 2, [1,0]
    M            For each in that list
     o±>         check if the argument is greater than it
  T              Transpose
mḋ               Convert each from binary

Previous 21 byte Solution

First time I've seen a use for ».

mḋT»o%2+ȯ?´eḋε%3`-0B3

Try it online!

Longer, as I was dealing with carries

Answer 2

JavaScript (ES6), 75 71 bytes

f=
n=>[1,0].map(i=>parseInt((n/2).toString(3).replace(/./g,c=>+c+i>>1),2))

<input type=number min=0 step=2 oninput=o.textContent=this.value%2?``:f(this.value)><pre id=o>

Explanation: Dividing input and the elements of A005823 by 2 doesn't alter the problem, however it makes the solution simpler as the ternary representations now only use 0s and 1s and therefore there is no carrying to consider. It also saves a step when converting from the element to its index (each element's ternary is twice the binary of its index). Examples:

                 A005823
                  halved
            n in  values A005823
   n n/2  base 3  base 3 indices
   0   0       0   0   0   0   0  
   2   1       1   1   0   1   0
   4   2       2   1   1   1   1
   6   3      10  10   0   2   0
   8   4      11  11   0   3   0
  10   5      12  11   1   3   1
  12   6      20  10  10   2   2
  14   7      21  11  10   3   2
  16   8      22  11  11   3   3
  18   9     100 100   0   4   0
  30  15     120 110  10   6   2
  32  16     121 111  10   7   2
  46  23     212 111 101   7   5
  50  25     221 111 110   7   6

Answer 3

Jelly, 26, 22, 21 bytes

ḶBḤḅ3
ÇŒcS=¥Ðf⁸ḢiЀÇT

Try it online!

One byte saved thanks to @JonathanAllan!

Explanation:

                # Helper link: A005823 to *N* terms
Ḷ               # Lowered range(N)
 B              # Converted to binary
  Ḥ             # Double each digit
   ḅ3           # Converted from base 3 to decimal
                # Main link
Ç               # Last link
 Œc             # All combinations of 2 items (with replacement)
      Ðf        # Remove every combination where this isn't true:
   S=¥          #   The sum of the two items is equal to N
        ⁸Ḣ      # Take the first combination left
          i     # Index of
           Ѐ   # Each element of the combination
             Ç  # In the sequence
              T # Return the truthy indices

Answer 4

J, ₃₅ 32 bytes

($#:I.@,)@(=[:+/~3#.+:@#:@i.@>:)

Try it online!

0-indexed and input is given monadically. Returns all possible summations to the value (it treats a b and b a as different possible summations).

Converting from a boolean matrix to indices takes a lot of code...

I'd like to also remove the fork on the left so I don't have to use as many parentheses and @-ats, but I can't figure out a good way to do it (my alternate approach doesn't save any bytes).

Explanation

For purposes of explaining and ungolfing, consider the following components of the main function

valid_nums      =. = [: +/~ 3 #. +:@#:@i.@>:
indices_of_ones =. $ #: I.@,

valid_nums yields a boolean matrix where the indices are the indices of the summed sequence values. If there's a one at those indices, it means that the two numbers sum to the input value.

indices_of_ones is a J idiom for giving the coordinates of the ones in an arbitrary rank boolean matrix

The main function is composed quite simply as

indices_of_ones@valid_nums

valid_nums

= [: +/~ 3 #. +:@#:@i.@>:  Input is n
                 #:@i.@>:  Binary numbers in range [0,n]
              +:           Doubled
         3 #.              Interpreted as ternary
     +/~                   Addition table with self (sum all possible pairs)
=                          Equate to n

indices_of_ones

$ #: I.@,
        ,  Ravel matrix into a single list
     I.    Find the indices of ones in that list
  #:       Convert to the base given by
$          The shape of the matrix

,-ravel works in this case by joining each row to the next.

   i.3 3
0 1 2
3 4 5
6 7 8
   , i.3 3
0 1 2 3 4 5 6 7 8

We can see that if this were a boolean matrix, the coordinates of ones can be found by interpreting the indices of the raveled matrix as numbers in the base of the shape of that matrix using as many prepositional phrases as possible to help confuse the poor reader.

Answer 5

Python 2, 51 bytes

f=lambda n:[n and(n/2%3>r)+2*f(n/3)[r]for r in 0,1]

Try it online!

The task can be done like this:

1. Halve the input
2. Convert to ternary list
3. Split that into two binary lists that sum elementwise to it
4. Convert those lists from binary

We can do the splitting in (3) by converting 0->0,1->1,2->1 for one list and 0->0,1->0,2->1 for the other. That is, by checking is the value is above a threshold of 0 or 1.

The two values can be found by respective recursive functions:

p=lambda n:n and(n/2%3>0)+2*p(n/3)
q=lambda n:n and(n/2%3>1)+2*q(n/3)

The function f combines the two of these in a list comprehension. This makes it inefficient due to exponential branching.

If complex numbers could be output, we could save 10 bytes with:

f=lambda n:n and(n%6>1)+n%6/4*1j+2*f(n/3)

Answer 6

MATL, 22 21 19 17 bytes

tQ:qBEI_ZA&+=R&fh

Output is 1-based. The program produces all solution pairs. Try it online! Or verify all test cases.

Explanation

t      % Implicit input: n. Duplicate
Q:q    % Range [0 1 ... n]
B      % Convert to binary. Gives a matrix where each row corresponds to a number
E      % Multiply each entry by 2
I_ZA   % Convert each row from ternary to a number
&+     % Matrix of all pair-wise additions
=      % Does each entry equal n?
R      % Upper triangular matrix
&f     % Push row and column indices of nonzero entries
h      % Concatenate horizontally. Implicit didsplay

Answer 7

Pyth, 37 bytes

0-indexed

Certainly not golfed as well as it could be.

KUQJmi:.Bd\1\23KhfqQ+@JeT@JhTsmm,dkKK

Try it online!

Answer 8

Pyth, 29 bytes

This one returns all possible pairs of indices.

fqQ+@Kmi:.Bd\1\[e-mail]2

Try it here.

Pyth, 30 bytes

hfqQ+@Kmi:.Bd\1\[e-mail]2

Try it here.

This returns the pairs of indices as [LowerIndex, HigherIndex].

---

How does this work?

hfqQ+@Kmi:.Bd\1\[e-mail]2   Full Program. Q means input throughout the whole explanation.

       m          Q               Map over the range [0, Q) with a variable d.
          .Bd                     Convert to binary.
         :   \1\2                 Replace 1 with 2.
        i        3                Convert it from base 3 to integer.
      K                           Assign the mapped range to a variable K.
                         .cUQ2    All possible two-element combinations of the range [0...Q).
    +@             hT@KeT         Sum of the integers on positions in K of the two-element
                                  combination.
 fqQ                              Filter those that equal the input.
h                                 Optional: Head. Take the first element.
                                  Print the result, implicitly. 

Answer 9

Paradoc (v0.2.10), 11 bytes (CP-1252)

½3B2>_B™2Bv

Try it online!

Algorithmically it's very much just like Neil's ES6 answer. On a lower level, also strikingly similar to H.PWiz's Husk answer. I am amused that we got to use all three overloadings of B.

Takes an integer on the stack, leaves a list of two integers on the stack.

Explanation:

½           .. Halve input
 3B         .. Convert to ternary
   2        .. 2, which will get implicitly coerced to [0,1]
    >_      .. Greater than, as a block
      B     .. "Bimap": take the block and map it over the Cartesian
            .. product of the last two lists to get a matrix
       ™    .. Transpose
        2Bv .. Convert each row from binary

Answer 10

JavaScript, 120 101 bytes

n=>[(A=[...Array(n+1)].map(Z=(a,b=a)=>b&&3*Z(b/2|0)+b%2*2))[F='findIndex'](a=>z=~A[F](b=>a+b==n)),~z]

Try it online!

0-indexed.
It returns the pair of indices where one index is the smallest possible (for example in the case of 428 it returns 22,31).

Answer 11

Python 3, 122 120 bytes

-2 bytes thanks to Mr. Xcoder!

0-indexed

def f(a):r=range(a);s=[int(bin(x)[2:].replace(*'12'),3)for x in r];return[(i,j)for i in r for j in r if s[i]+s[j]==a][0]

Ungolfed:

def f(a):
    r=range(a)
    s=[int(bin(x)[2:].replace(*'12'),3)for x in r]
    return[(i,j)for i in r for j in r if s[i]+s[j]==a][0]

Try it online!

Answer 12

Mathematica, 94 bytes

(w=#;Position[s,#]&/@#&@@(k=Select)[Tuples[s=k[Range@w,DigitCount[#,3,1]==0&],{2}],Tr@#==w&])& 

1-indexed

Answer 13

Brain-Flak, 220 166 bytes

-54 bytes by looking up the modulo function on the wiki, allowing some structural changes

({()<({}[()()])>}{}){({}(<>))<>(()()())({()<(({})){({}[()])<>}{}>}{}<><([{}()]{})>[()])}([]){{}<>(({}){})<>(({}){}{()<({}[()]){<>({}())<>(<{}>)}>}{})([][()])}({}{}<>)

Try it online!

0-indexed.

Explanation

Like many of the other solutions, this computes the ternary expansion of n/2 and converts that to two binary numbers.

Step 1: Divide input by 2

({()<({}[()()])>}{})

 {              }     until number becomes zero:
     ({}[()()])       subtract two
( ()<          > {})  push number of iterations

Step 2: compute ternary expansion

{({}(<>))<>(()()())({()<(({})){({}[()])<>}{}>}{}<><([{}()]{})>[()])}

 ({}(<>))<>         {   (({})){({}[()])<>}{} }{}<> ([{}()]{})         modulo (from wiki)
           (()()())                                                   use 3 as base
                     ()<                    >                         evaluate as 1 every time the 3 rolls over
                   (                              <          >[()])   push number of rollovers (function is now division with remainder)
{                                                                  }  repeat until quotient is zero, leaving all remainders on stack

Step 3: Convert to solution

([]){{}<>(({}){})<>(({}){}{()<({}[()]){<>({}())<>(<{}>)}>}{})([][()])}({}{}<>)

([]){{}                                                      ([][()])}           repeat while stack height > 1:
                                                                                 (loop happens once when initial stack height is 1, but that's fine)
       <>(({}){})                                                                double smaller output number
                 <>(({}){}                                  )                    double larger output number
                          {                              }{}                     if digit in ternary expansion is nonzero:
                           ()<                          >                        add 1 to larger output number
                              ({}[()]){                }                         if digit is 2:
                                       <>({}())<>(<{}>)                          add 1 to smaller output number

Answer 14

JavaScript (ES6), 70 72 bytes

n=>[6,4].map(x=>parseInt((n/2).toString(3).replace(/./g,d=>x>>d&1),2)) // thanks @Neil
n=>[0,1].map(x=>parseInt((n/2).toString(3).replace(/1|2/g,d=>~-d||x),2))

(0-indexed, and apparently nearly the same solution as @Neil even if I hadn't seen his answer)

I started off with getting the index back from a number using the reverse of the process: stringify with base 3, replace every 2 with 1, parse with base 2.

To get two numbers, and that for every even one, we just half the input - but now, also 1 digits can occur. So we replace it with a 0 in the one number and a 2 in the other number, which does not change the sum of the two, before the replace-and-parse step. Here is what I came up with (doing the two replacements, 1 -> 0-or-2 and 2 -> 1 in one step):

n=>["001","011"].map(x=>parseInt((n/2).toString(3).replace(/./g,d=>x[d]),2))

Of course the two replacement maps (strings) differ only in one index, so we should be able to shorten the array literal by only replacing 1 and 2 with d == 2 ? 1 : x. Or d-1 || x. Where -1 does the same as the two unary operators - but they look scarier :-)

Trying to avoid the array literal and the parenthesis around n/2 I also came up with

n=>Array.from(parseInt,(h=n/2,i)=>parseInt(h.toString(3).replace(/1|2/g,d=>~-d||i),2))

but it did not turn out fruitful.

Answer 15

Pyth, 22 bytes

J.m}1jb3hQxLJhfqsTQ^J2

Try it online: Demonstration

Explanation:

J.m}1jb3hQxLJhfqsTQ^J2
        hQ                input + 1 
 .m                       find all values of [0, 1, 2, ..., input], where
     jb3                     value converted to base 3
   }1                        check if it contains the digit 1
                          this boolean ^ is false
J                         store this list in variable J

                   ^J2    every pair of J
              f           filter for pairs with
                sT           sum of pair
               q             equal
                  Q          the input
             h            take the first of these pairs
          xLJ             and find the corresponding indices of J