21
\$\begingroup\$

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 \$3n\$ 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 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 , 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}\$.
\$\endgroup\$
3
  • \$\begingroup\$ 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? \$\endgroup\$ Apr 15 at 11:51
  • 1
    \$\begingroup\$ @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... \$\endgroup\$ Apr 15 at 13:05
  • 1
    \$\begingroup\$ @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". \$\endgroup\$ Apr 15 at 14:48

15 Answers 15

11
+200
\$\begingroup\$

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\$.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 51 bytes \$\endgroup\$ Apr 15 at 1:13
  • 1
    \$\begingroup\$ ... and 45 bytes in JavaScript V8 \$\endgroup\$ Apr 15 at 1:14
  • 3
    \$\begingroup\$ What an incredible idea! This is outputting the numbers whose base 7 representation has the last nonzero digit be either 2 or 5. \$\endgroup\$
    – xnor
    Apr 15 at 1:35
10
\$\begingroup\$

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 \$1a + 2b + 4c + 6d + \cdots\$. Within each group, \$4c + 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.

\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
2
5
\$\begingroup\$

Vyxal, 6 bytes

ǐ‹∑₃)ȯ

Try it Online!

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

Explained

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

Created with the help of Luminespire.

\$\endgroup\$
5
\$\begingroup\$

Charcoal, 36 bytes

Nθ≔⁰ηW‹ⅉθ«≦⊕η¿¬﹪↨E23⌕X⁰⮌↨ηIκ⁰±¹¦³⟦Iη

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

Nθ≔⁰ηW‹ⅉθ«≦⊕η

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

¿¬﹪↨E23⌕X⁰⮌↨ηIκ⁰±¹¦³⟦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:

Nθ≔¹ηW‹ⅉθ«W№υη≦⊕ηF12349⊞υ×ηIκ⟦Iη

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

Nθ≔¹ηW‹ⅉθ«

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

W№υη≦⊕η

Skip over numbers in the skip list.

F12349⊞υ×η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:

NθW‹Lυθ«→¿¬⊖⊟Φ↨×ⅈⅈ⁷κ⊞υⅈ»Iυ

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

NθW‹Lυθ«

Input n and start collecting n values.

→¿¬⊖⊟Φ↨×ⅈⅈ⁷κ⊞υⅈ

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
0
3
\$\begingroup\$

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.$$
\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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, 52 can...; = 2N

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

\$\endgroup\$
1
  • \$\begingroup\$ Another port of Pxeger's solution: 57 bytes \$\endgroup\$
    – Arnauld
    Apr 14 at 6:33
2
\$\begingroup\$

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

\$\endgroup\$
0
1
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ the - is a great find thanks \$\endgroup\$
    – Xenox
    Apr 14 at 21:36
  • \$\begingroup\$ you can replace disp(i); with just i and a new line \$\endgroup\$
    – Mohammad
    Apr 15 at 12:24
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

Ruby, 36 bytes

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

Try it online!

Using m90's method

\$\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.