Shift right by half a trit

Question

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 code-golf, so fewest bytes wins.

Test cases

0 -> 0
1 -> 0
2 -> 1
26 -> 17
27 -> 18
53 -> 26
54 -> 27
1337 -> 688

Answer 1

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.

• Albert.Lang: Walrus saves 2

Answer 2

Jelly, (削除) 13 10 (削除ここまで) 9 bytes

-3 bytes porting Dominic van Essen's implementation of my approach.
-1 byte thanks to Unrelated String (golfing the ¬ out by using a divisibility check.)

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
 ȧ - {that} logical AND {N}
 3ḍ - three divides {that}? (vectorises)
 S - sum

---

Alternative 9

^{Also seems to be a little more efficient, I'm not sure why.}

Try it online!

bḢ’+ọðƇ3L - Link: non-negative integer, N
 Ƈ - keep those i of [1..N] for which:
 ð 3 - f(i, 3):
b - convert {i} to base {3}
 Ḣ - head of {that} -> first trit (2 or 1)
 ’ - decrement {that} -> L (1 or 0)
 ọ - {i} order {3} (repeated divisibility count)
 + - {L} add {that}
 L - length

• Unrelated String: -1--I've sure wanted that NAND too, but the beauty of this particular program is you've got some other ways to throw around "inversions"!
• Jonathan Allan: Thanks @UnrelatedString, good call. I went searching for eights but only came up with other nines.
• Unrelated String: The second one is probably more efficient because it constructs fewer lists. The first one maps 3ḍ over the first list to make a new second list before summing; the second constructs one filtered list then immediately takes its length.
• Jonathan Allan: That makes sense, much more overhead than the repeated divisibility counting.

Answer 3

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

Answer 4

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.

Answer 5

Nekomata + -n, 10 bytes

R~3DelhÖ*ž

Attempt This Online!

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

R~3DelhÖ*ž
R~ Choose a number from 1 to the input
 3D Convert to base 3
 el 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

3D3UXci3bp≥

Attempt This Online!

3D3UXci3bp≥
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
 ci Optionally drop the last digit
 3b Convert from base 3
 p≥ Check that the result <= the input

-1 finds the first valid solution.

Answer 6

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

Answer 7

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)

Answer 8

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

• Jonathan Allan: 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 %)
• Dominic van Essen: @JonathanAllan - Great suggestion, but unfortunately the % approach only gains 1 nibble but loses 2 by losing the opportunity to use implicit variables...
• AlephSquirrel: Interesting that this is barely the shortest answer (2 others have 10 bytes)

Answer 9

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.

Answer 10

Vyxal, 10 bytes

'3=Ḋτh2+;L

Try it Online! Port of Jonathan Allan's Jelly answer.

 L # Count
' ; # Integers m from 1 to n where
 + # Either 
 3 Ḋ # m is divisible by 3
 h # Or the first item
 3= τ # Of n's base-3 representation
 2 # Is even

Answer 11

Uiua, 24 bytes

⨬⍜(-1°⊂⇌base3|⊙↘⟜ ̄¬)0⊸<2

Try it: Uiua pad. The comment # Experimental! enables the experimental base function, which has not yet been stabilized.

Explanation: A very elegant use of the ⍜ under modifier, which applies a transformation function, then applies a second function to modify the result, and undoes (applies the inverse function of) the transformation.

Here, the transformation is -1°⊂⇌base3: Convert to base 3, separate the first digit from the rest, and subtract 1 from that digit.

Subtracting 1 from the digit gives either 0 or 1. This means that changing the 1 to a 2 and vice versa is as simple as applying ¬ (boolean NOT). We then use this opposite boolean as the number of digits to remove from the end of the list: ⊙↘⟜ ̄.

The transformation is undone: Add 1 to the inverted boolean, prepend it back to the array of digits, and convert back from base 3.

This does the task, but it fails for the numbers zero and one, since for zero you can't take the first digit from the empty list returned by base3, and for one the result is incorrect because we drop 1 from the end and flip the 1 to a 2, rather than flipping first and then dropping. Therefore, I wrapped the whole thing with ⨬F0⊸<2, which does the logic if the number is greater than 2, or returns zero otherwise.

Answer 12

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!

Answer 13

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]

Answer 14

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

Answer 15

Charcoal, 16 bytes

ILΦEN↨⊕ι3¬∧⌕ι2⊟ι

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.

 N Input as a number
 E Map over implicit range
 ι Current value
 ⊕ Incremented
 ↨ Converted to base
 3 Literal integer `3`
 Φ Filtered where
 ι Current base `3` list
 ⌕ Does not begin with
 2 Literal integer `2`
 ∧ Logical And
 ι Current base `3` list
 ⊟ Does not end with `0`
 ¬ Logical Not
 L Take the length
I Cast to string
 Implicitly print

Answer 16

APL(Dyalog Unicode), ^{(削除) (削除ここまで)}25 bytes ^SBCS

Direct implementation of the problem description.

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

Try it on APLgolf!

Answer 17

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

Answer 18

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

Answer 19

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.

Answer 20

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