17
\$\begingroup\$

Shift right by half a trit

This is inspired by Shift right by half a bit, but it's a little different.

Motivation

I was wondering if there is a function f that maps the non-negative integers to the non-negative integers, with the following properties:

  • It is non-decreasing (if a < b, then f(a) ≤ f(b))
  • For any non-negative integer a, f(f(a)) = floor(a/3)

It turns out there is exactly one f that satisfies these properties. Your task is to implement it.

Task

Write a program or function that takes a non-negative integer n, and applies these rules:

  • If n=0, return 0.
  • Otherwise, write n in ternary. If it starts with a 1, change the leading 1 to a 2, then remove the final digit and return the resulting number.
  • If n starts with a 2, change it to a 1 and return the resulting number.

Note that you don't need to implement this exact procedure, but I included it to give an explicit description of f.

Rules

Numbers can be represented in any reasonable format, but if you represent them as a string or list of digits, it must be in decimal or unary. I include this to specifically disallow ternary, since that skips a large part of the problem.

This is , so fewest bytes wins.

Test cases

0 -> 0
1 -> 0
2 -> 1
26 -> 17
27 -> 18
53 -> 26
54 -> 27
1337 -> 688
Improve this question
\$\endgroup\$

18 Answers 18

Reset to default
7
\$\begingroup\$

Python 3, 55 bytes

f=lambda n,c=1:n>c and f(n,c*3)or[0,(n+c)//3,n-c][n//c]

Try it online!

The termination condition n>c looks wrong but it happens to work out with and/or.

Python 3, 41 bytes

f=lambda n:n>1and-(n//3<f(x:=1+f(n-1)))+x

Try it online!

Recursive magic based on the original definition, copied from l4m2's JS answer. Thanks to Albert Lang for -2 bytes using the walrus.

Improve this answer
\$\endgroup\$
1
6
\$\begingroup\$

Jelly,  13  10 bytes

-3 bytes porting Dominic van Essen's implementation of my approach.

b3ḢḂȧ%3¬)S

Try it online! Or see the test-suite.

How?

b3ḢḂȧ%3¬)S - Link: non-negative integer, N
        )  - for each {I in [1..N] ([] if N==0)}:
b3         -   convert {I} to base three
  Ḣ        -   head of {that}
   Ḃ       -   {that} mod two -> L
     %3    -   {I} mod three -> R
    ȧ      -   {L} logical AND {R}
       ¬   -   logical NOT of {that}
         S - sum

(I sometimes wish there was a logical NAND dyad, or at least one that acts that way with zeros and ones.)

Original at 13 bytes

æḟ©3Ḥạ+⁺_®)»ċ

A monadic Link that accepts a non-negative integer, \$N\$, and yields the value of \$f(n)\$.

Try it online! Or see the test-suite.

How?

Outputs the number of terms less than or equal to \$N\$ in another sequence - the unique, strictly increasing sequence of non-negative integers, \$a\$, such that \$a(a(n)) = 3n\$. This is A003605, which gives the indices at which an increase occurs in \$f\$.

æḟ©3Ḥạ+⁺_®)»ċ - Link: non-negative integer, N
          )   - for each {I in [1..N] ([] if N==0)}:
æḟ 3          -   floor to the nearest power of three
  ©           -   (and copy this to the register)
    Ḥ         -   double {that}
     ạ        -   {that} absolute difference {I}
       ⁺      -   do this twice:
      +       -     add {I}
        _®    -   subtract the value stored in the register
           »  - maximum with {N} (vectorises)
            ċ - count occurrences of {N}
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

JavaScript (Node.js), 34 bytes

f=n=>n<2?0:!(n/3^f(1+f(--n)))+f(n)

Try it online!

Self is slow, but can save states to fasten

JavaScript (Node.js), 47 bytes

f=(n,i=1)=>n<i?n-i/3|0:n<2*i?n/3+i/3|0:f(n,i*3)

Try it online!

Fast, not sure relation between Arnauld's solution

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Setanta, 65 bytes

gniomh(n){s:=1nuair-a s*3<=n s*=3toradh(n|0&n/s<2&(n+s)//3)|n-s}

try-setanta.ie link

Explanation

gniomh(n){s:=1nuair-a s*3<=n s*=3toradh(n|0&n/s<2&(n+s)//3)|n-s}­⁡​‎‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏⁠‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏⁠‎⁡⁠⁢⁡⁤‏⁠‎⁡⁠⁢⁢⁡‏⁠‎⁡⁠⁢⁢⁢‏⁠‎⁡⁠⁢⁢⁣‏⁠‎⁡⁠⁢⁢⁤‏⁠‎⁡⁠⁢⁣⁡‏⁠‎⁡⁠⁢⁣⁢‏⁠‎⁡⁠⁢⁣⁣‏⁠‎⁡⁠⁢⁣⁤‏⁠‎⁡⁠⁢⁤⁡‏⁠‎⁡⁠⁢⁤⁢‏⁠‎⁡⁠⁢⁤⁣‏⁠‎⁡⁠⁢⁤⁤‏⁠‎⁡⁠⁣⁡⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣⁡⁢‏⁠‎⁡⁠⁣⁡⁣‏⁠‎⁡⁠⁣⁡⁤‏⁠‎⁡⁠⁣⁢⁡‏⁠‎⁡⁠⁣⁢⁢‏⁠‎⁡⁠⁣⁢⁣‏⁠‎⁡⁠⁣⁢⁤‏⁠‎⁡⁠⁣⁣⁡‏⁠‎⁡⁠⁣⁣⁢‏⁠‎⁡⁠⁣⁣⁣‏⁠‎⁡⁠⁣⁣⁤‏⁠‎⁡⁠⁣⁤⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣⁤⁢‏⁠‎⁡⁠⁣⁤⁣‏⁠‎⁡⁠⁣⁤⁤‏⁠‎⁡⁠⁤⁡⁡‏⁠‎⁡⁠⁤⁡⁢‏⁠‎⁡⁠⁤⁡⁣‏⁠‎⁡⁠⁤⁡⁤‏⁠‎⁡⁠⁤⁢⁡‏⁠‎⁡⁠⁤⁢⁢‏⁠‎⁡⁠⁤⁢⁣‏⁠‎⁡⁠⁤⁢⁤‏⁠‎⁡⁠⁤⁣⁡‏⁠‎⁡⁠⁤⁣⁢‏⁠‎⁡⁠⁤⁣⁣‏⁠‎⁡⁠⁤⁣⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤⁤⁡‏⁠‎⁡⁠⁤⁤⁢‏⁠‎⁡⁠⁤⁤⁣‏⁠‎⁡⁠⁤⁤⁤‏‏​⁡⁠⁡‌­
          s:=1nuair-a s*3<=n s*=3                                 # ‎⁡Calculate the largest power of 3 than is <= n
                                 toradh(n|0&                      # ‎⁢Return 0 for n == 0 (otherwise it returns -1)
                                            n/s<2&(n+s)//3)       # ‎⁣If the first ternary digit is 1, then add s and divide by 3
                                                           |n-s   # ‎⁤Otherwise, subtract by s
💎

Created with the help of Luminespire.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Nekomata + -n, 10 bytes

R~3DᵉlhÖ*ž

Attempt This Online!

A port of @Dominic van Essen's implementation of @Jonathan Allan's approach.

R~3DᵉlhÖ*ž
R~              Choose a number from 1 to the input
  3D            Convert to base 3
    ᵉl          Take the last digit
      h         Take the first digit
       Ö        Mod the first digit by 2
        *       Multiply that by the last digit
         ž      Check that the result is 0

-n counts the number of valid solutions.

Nekomata + -1, 11 bytes

3D3UXᶜi3bᵖ≥

Attempt This Online!

3D3UXᶜi3bᵖ≥
3D              Convert to base 3
  3UX           Bitwise xor with [3]
                    If the input is 0, the digits are [], so this is [3]
                    For other inputs, this simply bitxor the first digit with 3
     ᶜi         Optionally drop the last digit
       3b       Convert from base 3
         ᵖ≥     Check that the result <= the input

-1 finds the first valid solution.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

R, 41 40 bytes

`?`=\(n)`if`(n<2,0,(k=?n-1)+!n%/%3-?1+k)

Attempt This Online!

Port of @l4m2's JS answer.

Slightly ungolfed:

f=\(n)`if`(n<2,0,f(n-1)+(n%/%3==f(1+f(n-1))))
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 15 bytes

_+3Bć©3αì®i¨}3ö

Try it online or verify all test cases.

Explanation:

_               # Check whether the (implicit) input-integer is 0
                # (1 if 0; 0 otherwise)
 +              # Add that to the implicit input-integer
  3B            # Convert it to a base-3 string
    ć           # Extract its head
     ©          # Store this digit in variable `®` (without popping)
      3α        # Pop and get the absolute difference with 3
                # (1 becomes 2; and vice-versa)
        ì       # Prepend it back to the base-3 string
         ®      # Push the original head again
          i }   # If it was 1:
           ¨    #  Remove the last character
             3ö # Convert it back from base-3 to a base-10 integer
                # (which is output implicitly as result)
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Nibbles, 18 nibbles (9 bytes)

,|,$~*%$3- 2/`@3

Attempt This Online!

An implementation of Jonathan Allan's approach of counting elements of A003605 up to n: upvote that!

,|,$~*%$3- 2/`@3    # full program
,|,$~*%$3- 2/`@3$$  # with implicit variables shown;
,                   # return length of 
  ,$                # 1..n
 |                  # filtered to include only elements
    ~               # for which result is zero for: 
     *              #   product of 
      %$3           #     element modulo 3
                    #   and 
         - 2        #     2 minus
            /    $  #     first digit of
             `@3$   #     element in base 3
Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Nice work, this way allows me to golf mine. Would it help you to use x mod two rather than two minus x? (I see "Autos" lists two for %) \$\endgroup\$
    – Jonathan Allan
    Commented Aug 13 at 17:52
  • 1
    \$\begingroup\$ @JonathanAllan - Great suggestion, but unfortunately the % approach only gains 1 nibble but loses 2 by losing the opportunity to use implicit variables... \$\endgroup\$
    – Dominic van Essen
    Commented Aug 13 at 20:04
  • \$\begingroup\$ Interesting that this is barely the shortest answer (2 others have 10 bytes) \$\endgroup\$
    – AlephSquirrel
    Commented Aug 14 at 19:18
2
\$\begingroup\$

Vyxal, 15 bytes

[3τḣ$⌐⇧~p$ċßṪ3β

Try it Online!

There for sure is a better and more mathematical way of doing this than the explicit description of f.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 48 bytes

f=(n,k=1)=>n<k*3?n/k^1?n&&n-k:(n+k)/3|0:f(n,k*3)

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

APL+WIN, 57 bytes

⍎∊((n←⎕)=0)↑⊂'n⋄→'⋄3⊥(-i)↓((1+i←2|↑n),1↓n←((⌊1+3⍟n)⍴3)⊤n)

Try it online! Thanks to Dyalog Classic

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 16 bytes

ＩＬΦＥＮ↨⊕鳬∧⌕ι²⊟ι

Try it online! Link is to verbose version of code. Explanation: Uses @JonathanAllan's observation that f(a) is the number of members of A003605 between 1 and a inclusive.

    Ｎ               Input as a number
   Ｅ                Map over implicit range
       ι            Current value
      ⊕             Incremented
     ↨              Converted to base
        ³           Literal integer `3`
  Φ                 Filtered where
            ι       Current base `3` list
           ⌕        Does not begin with
             ²      Literal integer `2`
          ∧         Logical And
               ι    Current base `3` list
              ⊟     Does not end with `0`
         ¬          Logical Not
 Ｌ                  Take the length
Ｉ                   Cast to string
                    Implicitly print
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

APL(Dyalog Unicode), 25 bytes SBCS

Direct implementation of the problem description.

(3⊥3|(-1=⊃)↓+⍨@1)3⊥⍣¯1⌈∘1

Try it on APLgolf!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Google Sheets, 98 bytes

=let(t,base(A1,3),decimal(switch(--left(t),0,0,1,iferror(2&mid(t,2,len(t)-2)),2,1&mid(t,2,99)),3))

Put \$n\$ in cell A1 and the formula in B1.

screenshot

Ungolfed:

=let( 
  t, base(A1, 3), 
  decimal( 
    switch(--left(t), 
      0, 0, 
      1, iferror(2 & mid(t, 2, len(t) - 2)), 
      2, 1 & mid(t, 2, 99)   
    ), 
    3 
  )
)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Scala 3, 166 bytes

166 bytes, it can be golfed more.

Golfed version. Attempt This Online!

def f(n:Int,s:Int=1):Int={
var a=Seq(0,0)
var z=s
for(_<-0to n-1){
if (a.size>n){return a(n)}
a++=(z to z*2-1)
for(x<-z*2 until{z=z*3;z}){a++=Seq.fill(3)(x)}
}
a(n)
}

Ungolfed version. Attempt This Online!

object Main {
  def f(n: Int, s: Int = 1): Int = {
    var a = List(0, 0)
    var sVar = s
    for (_ <- 0 until n) {
      if (a.length > n) {
        return a(n)
      }
      a = a ++ (sVar until sVar * 2)
      for (x <- sVar * 2 until {sVar = sVar * 3; sVar}) {
        a = a ++ List.fill(3)(x)
      }
    }
    a(n)
  }

  def main(args: Array[String]): Unit = {
    val testCases = List(0, 1, 2, 26, 27, 53, 54, 1337)
    for (n <- testCases) {
      println(s"$n -> ${f(n)}")
    }
  }
}
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Arturo, 43 bytes

f:$->n[?n<2->0->+?=n/3f 1+f n-1->1->0f n-1]

Try it!

Port of l4m2's JavaScript answer.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Python, 107 bytes

Incredibly slow for non-low n, thanks to generating exponentially more terms than needed. For testing purposes, you can get around that by adding if len(a)>n:break to the for loop.

def f(n,s=1,r=range):
 a=[0,0]
 for _ in r(n):
  a+=r(s,s*2)
  for x in r(s*2,s:=s*3):a+=[x]*3
 return a[n]

Attempt This Online!

Explanation: the sequence f(0), f(1), ... is

0,  0,  1,  2,  2,  2,  3,  4,  5,
6,  6,  6,  7,  7,  7,  8,  8,  8,
9, 10, 11, 12, 13, 14, 15, 16, 17,
18, 18, 18, 19, 19, 19, 20, 20, 20,
21, 21, 21, 22, 22, 22, 23, 23, 23,
24, 24, 24, 25, 25, 25, 26, 26, 26,
...

which can be grouped into chunks: 0, 0 | 1; 2, 2, 2 | 3, 4, 5; 6, 6, 6, 7, 7, 7, 8, 8, 8 | .... We generate a prefix of the sequence and pick the (0-indexed) nth term.

Ungolfed algorithm:

def f(n):
    arr = [0, 0]
    # the exact number of iterations doesn't matter as long as we generate enough terms
    for i in range(n):
        s = 3 ** i
        for x in range(s, s * 2):
            arr.append(x)
        for x in range(s * 2, s * 3):
            for _ in range(3):
                arr.append(x)
    return arr[n]
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Retina 0.8.2, 49 bytes

.+
$*#
#
¶$`#
%+`^\B(#*)\1\1(#*)
$1$.2
\b2.*|.0\b

Try it online! Link includes test cases. Explanation: Port of my Charcoal answer.

.+
$*#

Convert to unary.

#
¶$`#

Generate all the integers up to and including n.

%+`^\B(#*)\1\1(#*)
$1$.2

Convert to base 3.

\b2.*|.0\b

Count those starting with 2 or ending in 0 (but taking care not to count 0 itself or to double-count numbers that both start with 2 and and in 0).

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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