# 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.

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


# 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.

• Walrus saves 2 Commented Aug 13 at 22:36

# 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
Ḃ       -   {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:
_®    -   subtract the value stored in the register
»  - maximum with {N} (vectorises)
ċ - count occurrences of {N}


# 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

# Setanta, 65 bytes

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


## 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.

# Nekomata + -n, 10 bytes

R~3DᵉlhÖ*ž


Attempt This Online!

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.

# R, 41 40 bytes

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


Attempt This Online!

Slightly ungolfed:

f=\(n)if(n<2,0,f(n-1)+(n%/%3==f(1+f(n-1))))


# 05AB1E, 15 bytes

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


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
©          # 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)


# 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

• 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 %) Commented Aug 13 at 17:52
• @JonathanAllan - Great suggestion, but unfortunately the % approach only gains 1 nibble but loses 2 by losing the opportunity to use implicit variables... Commented Aug 13 at 20:04
• Interesting that this is barely the shortest answer (2 others have 10 bytes) Commented Aug 14 at 19:18

# 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.

# 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!

# 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

# 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


# APL(Dyalog Unicode), 25 bytes SBCS

Direct implementation of the problem description.

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


Try it on APLgolf!

=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.

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
)
)


# 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)}")
}
}
}


f:$->n[?n<2->0->+?=n/3f 1+f n-1->1->0f n-1]  Try it! Port of l4m2's JavaScript answer. # 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]  # 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).