Output a 1-2-3 sequence

Question

For the purposes of this challenge, a 1-2-3 sequence is an infinite sequence of increasing positive integers such that for any positive integer \$n\$, exactly one of \$n, 2n,\$ and \3ドルn\$ appears in the sequence. There exist multiple such sequences, so any one will suffice.

Your challenge is to output any 1-2-3 sequence. Standard sequence rules apply - you may output as a function that takes \$n\$ and outputs the \$n\$th term or first \$n\$ terms, or output an infinite sequence in some form. You may use 0- or 1-indexing.

This is code-golf, so shortest wins!

Some additional math problems for anyone interested:

1. What is the cardinality of the set of 1-2-3 sequences?
2. Prove or disprove: the natural density of each 1-2-3 sequence in the natural numbers is \$\frac{1}{3}\$.

• Sylvester is on codidact.com: I feel like I'm missing something huge here, but I don't quite understand the challenge, and looking at the answers only confused me more. The sequence 1, 6, 7, ... doesn't contain 1, 2, and 3 times any positive integer. In fact, I can't find a single integer n where n, 2n, and 3n are all in that sequence. Could someone clarify for me?
• Benjamin Wang: @SylvesterKruin Take your sequence 1, 6, 7, ...; when n=1, we have that 1n=1 (and not 2 nor 3) is in the sequence; when n=2, we have that 3n=6 (and not 2 nor 4) is in the sequence; when n=3, we have that 2n=6 (and not 3 nor 9) is in the sequence; and so on...
• Sylvester is on codidact.com: @BenjaminWang Ohhhhh I see, thank you so much! I think the fact that it said "n, 2n, and 3n" confused me. If I want to be picky, it should have said "or".

Answer 1

JavaScript, (削除) 52 (削除ここまで) 51 bytes

for(n=0;h=x=>x%7||h(x/7);)~h(++n)%3||console.log(n)

Try it online!

-1 thanks to Mukundan314.

The sequence contains the numbers that are congruent to 2 or 5 modulo 7 after removing all factors of 7.

This works because \$(\mathbb{Z}/7\mathbb{Z})^{\times}/\{1,-1\}\cong C_3\$, with \$\{1,2,3\}\$ mapping to the three distinct elements of \$C_3\$, so that for \$n\$ not divisible by 7, \$\{n,2n,3n\}\$ also map to the three distinct elements of \$C_3\$.

• Mukundan314: 51 bytes
• Mukundan314: ... and 45 bytes in JavaScript V8
• xnor: What an incredible idea! This is outputting the numbers whose base 7 representation has the last nonzero digit be either 2 or 5.

Answer 2

Jelly, 8 bytes

Æf’S3ḍμ#

Try it online!

A positive integer \$n = 2^a 3^b 5^c 7^d \cdots\$ belongs to a group identified by \5ドル^c 7^d \cdots\$ (i.e. the largest divisor of \$n\$ without prime factors 2 and 3). We can choose different \$a-b \operatorname{mod} 3\$ for each group, as long as the choice is consistent within a group.

Given \$n\$, Æf gives a flat list of primes whose product is \$n\$, i.e. \$a\$ copies of 2, \$b\$ copies of 3, and so on. ’ decrements each element, and S gives the sum, which is \1ドルa + 2b + 4c + 6d + \cdots\$. Within each group, \4ドルc + 6d + \cdots\$ is constant, and 2 is equal to -1 modulo 3, so the code selects the numbers where \$a - b \operatorname{mod} 3\$ is some constant within each group.

Answer 3

Python 2, 61 bytes

i,=a={0}
while 1:
 if{i}-a:print i;a|={i*2,i*3,i*4,i*9}
 i+=1

Attempt This Online!

-4 thanks to Jonathan Allan and Mukundan314.

This is A339746, same as Neil's answer.

Method found by math scat as a simple fix for my initial idea (which they also thought of independently).

• Jonathan Allan: 63 bytes ATO
• Mukundan314: 61 bytes (extending on Jonathan's)

Answer 4

Vyxal, 6 bytes

ǐ‹∑3)ȯ

Try it Online!

A port of Bubbler's excellent Jelly answer. Go upvote that too.

Explained

ǐ‹∑3)ȯ­⁡​‎⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌­
 )ȯ # ‎⁡Get the first n numbers where
 ∑ # ‎⁢ The sum of:
ǐ # ‎⁣ The prime factors (with repeats)
 ‹ # ‎⁤ Decremented
 3 # ‎⁢⁡ Is divisible by 3
💎

Created with the help of Luminespire.

Answer 5

Charcoal, 36 bytes

Nθ≔0ηW‹jθ«≦⊕η¿¬%↨E23⌕X0⮌↨ηIκ0±1¦3⟦Iη

Try it online! Link is to verbose version of code. Explanation:

Nθ≔0ηW‹jθ«≦⊕η

Input n and count up until n numbers have been output.

¿¬%↨E23⌕X0⮌↨ηIκ0±1¦3⟦Iη

If the exponents of 2 and 3 in the current value's factorisation differ by a multiple of 3 then output the current value on its own line.

A port of @pxeger's Python answer is only 32 bytes:

×ばつηIκ⟦Iη

Try it online! Link is to verbose version of code. Explanation:

Nθ≔1ηW‹jθ«

Input n and count up until n numbers have been output.

WNoυη≦⊕η

Skip over numbers in the skip list.

×ばつηIκ

Add the five multiples to the skip list (which will also cause the current value to be "skipped" on the next pass).

⟦Iη

Output the current value on its own line.

A port of @m90's answer is only 26 bytes:

×ばつii7κ⊞υi»Iυ

Try it online! Link is to verbose version of code. Explanation:

NθW‹Lυθ«

Input n and start collecting n values.

×ばつii7κ⊞υi

Increment the value and if the last nonzero digit of its square in base 7 is 1 then add it to the predefined empty list.

»Iυ

Output the final list.

Answer 6

Jelly, 9 bytes

ọⱮ3IṪ3ḍμ#

A full program that accepts a number, \$n\$, from stdin and prints a Jelly representation of a list of the first \$n\$ natural numbers for which the difference in its order of two and three differ by a multiple of three (Neil's discovery).

Try it online!

How?

ọⱮ3IṪ3ḍμ# - Main Link: no arguments
 μ# - count up from k=0 finding the first stdin k for which:
 Ɱ3 - map across j in [1,2,3] with:
ọ - number of times j divides into k (nọ0 -> inf)
 I - forward differences
 Ṫ - tail -> 3ọk-2ọk
 3ḍ - three divides?
 - implicit print

Answer 7

Wolfram Language (Mathematica), 43 bytes

f@n_:=f[2n|3n|4n|9n]=Print@n
f@i~Do~{i,∞}

Try it online!

Outputs an infinite sequence. Same sequence as probably all the other answers.

---

Such sequences are sets of positive natural numbers \2ドル^i3^jn\$ such that \2,3ドル\not\mid n\$ and \$i-j\equiv c_n\pmod3\$ for some \$c_n\in\{0,1,2\}\$. We can fully define such a set by choosing \$c_n\$ for each \$n\$. Equivalently, choose one of \$n,2n,3n\$ to include in the set.

Therefore:

• The set of such sets has cardinality \3ドル^{\{n\in\mathbb N^+|2,3\not\mid n\}}=2^{\aleph_0}\$.
• Select the set \$S\$ defined by \$c_n=0\$, i.e. \2,3ドル\not\mid n\implies n\in S\$. The density of such \$n\$ is clearly \$\frac12\cdot\frac23=\frac13\$. However, we also have \$x\in S\implies 6x,8x,27x\in S\$. The density of \$S\$ is thus $$\frac13\left(1+\frac16+\frac1{6^2}\right)\left(1+\frac18+\frac1{8^2}+\cdots\right)\left(1+\frac1{27}+\frac1{27^2}+\cdots\right)= \frac{43}{91}\approx0.47253.$$

Answer 8

x86-64 machine code, 24 bytes

31 C0 8D 70 07 FF C0 50 F7 E0 F7 F6 89 D1 E3 FA 58 E2 F2 FF CF 79 EE C3

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes a 0-indexed n in EDI and returns the nth term in EAX.

This uses the same idea as my previous answer; the sequence contains the numbers that are congruent to 1 or 6 modulo 7 after removing all factors of 7. This works because \$(\mathbb{Z}/7\mathbb{Z})^{\times}/\{1,-1\}\cong C_3\$, with \$\{1,2,3\}\$ mapping to the three distinct elements of \$C_3\$, so that for \$n\$ not divisible by 7, \$\{n,2n,3n\}\$ also map to the three distinct elements of \$C_3\$.

In assembly:

f: xor eax, eax # Set EAX to 0.
 lea esi, [rax + 7] # Set ESI to 7.
n: inc eax # Add 1 to EAX. This will be the number m being checked.
 push rax # Save the value of RAX onto the stack.
 mul eax # Multiply EAX by itself, putting the product in EDX:EAX.
d: div esi # Divide EDX:EAX by ESI, putting the remainder in EDX
 # and the quotient in EAX.
 mov ecx, edx # Copy the remainder into ECX.
 # (The higher bits of RCX are zeroed.)
 jrcxz d # If RCX=0, jump back to divide again.
 pop rax # Restore the value of RAX (m) from the stack.
 loop n # Decrease RCX by 1, and jump if it's nonzero.
 dec edi # (If we get here, we have found a number to include.)
 # Subtract 1 from EDI, counting down from n.
 jns n # Jump back if the result is not negative.
 ret # Return.

Answer 9

Vyxal 3, 11 bytes

ÞṆΩ2Mn3M-3Ḋ

Outputs A339746 as an infinite sequence.

Try it Online! (times out) | Range instead of infinite list

ÞṆΩ2Mn3M-3Ḋ­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌­
ÞṆΩ # ‎⁡Filter set of natural numbers ...
 2M # ‎⁢ number of times 2 divides n
 n3M # ‎⁣ number of times 3 divides n
 -3Ḋ # ‎⁤Is the difference a multiple of 3?
💎

Created with the help of Luminespire.

Answer 10

JavaScript (V8), 53 bytes

for(i=1;g=i=>i%3?i&-i:g(i/3*4);i++)g(i)%7-1||print(i)

Try it online!

Can port to C(70 bytes)

JavaScript (V8), 57 bytes

for(n=0,p=print;;)p[++n]||p(n)|[2,3,4,9].map(i=>p[n*i]=1)

Try it online!

Port of Pxeger's. -2 from Arnauld(削除) to make it beat Neil's (削除ここまで)

JavaScript (V8), 59 bytes

for(i=1;g=k=>i%k?0:1+g(k*h);i++)(g(h=2)-g(h=3))%3||print(i)

Try it online!

Same theory Neil's solution though found independently

---

For cardinality thing, obviously 1 can be chosen or unchosen, 5 can, 5² can...; = 2^N

For density thing, this solution goes to 0.472, which I'd say far enough to reject 1/3 assumption

• Arnauld: Another port of Pxeger's solution: 57 bytes

Answer 11

C (GCC), 63 bytes

i;main(j){for(;;~j%7%3||printf("%d ",i))for(j=++i;j%7<1;)j/=7;}

Attempt This Online!

Port of @m90's answer

C (gcc), ^{(削除) 82 (削除ここまで)} 74 bytes

-8 bytes thanks to @Digital Trauma

i;main(j,k){for(;;k%3||printf("%d ",i))for(k=ffs(j=++i)-1;j%3<1;j/=3)k--;}

Try it online!

Port of @math scat's answer

Answer 12

Matlab, (削除) 69 (削除ここまで) 66 bytes

i=1;a=[];while 1;if all(a-i);disp(i);a=[a [2:4 9]*i];end;i=i+1;end

Try it online!

It basically is a translation of pxeger's answer. Matlab also has a union function, but it would cost 5 bytes.

-3 bytes thanks to Luis Mendo

• Xenox: the - is a great find thanks
• Mohammad: you can replace disp(i); with just i and a new line

Answer 13

Haskell, 32 bytes

[n|n<-[1..],mod(gcd(6^n)n^2)7<2]

Try it online!

An adaptation of m90's method. Extracts the 2^a * 3^b component by taking the gcd with a large power of 6, and checks that modulo 7 it's either 1 or 6.

39 bytes

[n|n<-[1..],mod(div n(gcd(7^n)n)^2)7<2]

Try it online!

Uses m90's fantastic solution of outputting numbers whose base 7 representations have their last nonzero digit as either 1 or 6. Because multiplying by 2 or 3 cycles between this digit being in {1,6}, {2,5}, or {3,4}, exactly one of n, 2*n, 3*n will satisfy this property.

The code first casts out factors of 7 by dividing n by its gcd with some high power of 7. Then, it checks if its square equals 1 modulo 7, and if so outputs this n.

Answer 14

05AB1E, 7 bytes

∞ʒÒ<O3Ö

Port of @Bubbler's Jelly answer, but with an infinite list instead.

Try it online.

Explanation:

∞ # Push an infinite positive list: [1,2,3,...]
 ʒ # Filter it by:
 Ò # Get the prime factors of the current integer, including duplicates
 < # Decrease each by 1
 O # Take the sum of that
 3Ö # Check whether it's divisible by 3
 # (after which the filtered infinite list is lazy output implicitly as result)

Answer 15

Ruby, 36 bytes

0.step{|x|x.to_s(7)=~/[25]0*/&&p(x)}

Try it online!

Using m90's method