18
\$\begingroup\$

A sign sequence is an infinite sequence consisting entirely of \$1\$ and \$-1\$. These can be constructed a number of ways, for example:

  • Alternating signs: \$1, -1, 1, -1, ...\$
  • \$-1\$ for primes, \$1\$ for non-primes: \$1, -1, -1, 1, -1, 1, -1, ...\$
  • All \$1\$s: \$1, 1, 1, ...\$

Your task is to write a piece of code that outputs a deterministic sign sequence that no other answer already outputs. You must include a proof that your sequence is unique from all sequences posted before yours and that your sequence only contains \$1\$ and \$-1\$. You do not have to worry about keeping up to date for newer answers, as they must ensure their sequences are unique, not you.

You may output in any reasonable manner, including (but not limited to):

  • Outputting an infinite list/generator/tuple of values
  • Outputting the next value in the sequence each time your code is run
  • Outputting the sequence infinitely

You may not take any input (unless necessary), so outputing the first \$n\$ terms or the \$n\$th term is not allowed.

I've included my implementation of a sequence as the first answer, to ensure that all answers have to provide a proof of uniqueness.


This is a , so the answer with the most votes wins. You should aim to do the following things in your answer:

  • Be creative. Avoid simply outputting constant runs of \$1\$s or \$-1\$s or outputting one value when a number is insert common numeric property here and the other when not (e.g. primes or Fibonacci numbers).
  • Avoid copying others. While all sequences must be unique, aim to be innovative, rather than simply slightly modify another user's sequence (for example, swapping the placements of \$1\$ and \$-1\$)
  • Make it clear what your program is doing. Not everyone can read a Jelly, R or Java answer, but they can read an explanation of the answer, as well as an explanation of how/why you chose this specific sequence and the proof of uniqueness included in your answer

Voters should consider the following when casting their votes:

  • How creative is the sequence? Has it been done to death before, or is it something you've never seen before?

    • Is the sequence using some properties of \$1\$ and \$-1\$ to be generated, or is it just applying the \$\text{sgn}\$ function to other sequences?
  • Is it unique, or is it simply a slight modification on a sequence that many other users have done? If it is a modification, is it uncreative, or has the author seen a property that others haven't?

  • How clever is the implementation of the sequence, and how well explained is it? For this, consider both the actual code of the answer and the algorithm it implements. If the code uses a language specific trick you find particularly impressive, it may be worth an upvote. If the implementation of the algorithm is so general than any language could be used, yet is still creative and unique, it's probably worth an upvote. However, if the code is overly convoluted when a simpler method would work, or if the algorithm is incredibly inefficient when a better version exists, consider casting a downvote.

    Furthermore, while you may not be able to understand the 10 bytes of 05AB1E posted, if explained well, you should be able to get a solid understanding of how those 10 bytes implement the chosen sequence, and how clever it is. And while you may be able to fluently read Python, if poorly coded with no explanation, you may not be able to fully understand how that program works. Consider this factor when voting.

Voters should not vote for an answer for any of the following reasons:

  • The program is written in your favourite/least favourite language
    • Voting for the use of tricks within a language are fine. Voting for an answer because of the language, is not an acceptable reason
  • The program is short/long/written with ASCII characters/written without ASCII characters
  • You recognize the user who wrote the answer and you love/hate them
  • Any other reason not specified above (e.g. "This answer uses the e character, I love it!")
\$\endgroup\$
1

28 Answers 28

18
\$\begingroup\$

05AB1E, 14 bytes

∞v®yÒgm=Ox<.±,

Try it online!

My first non-trivial 05AB1E answer! Happy for suggestions to improve it.

The code prints two interleaved sign sequences, both related to the Pólya conjecture. In 1919, George Pólya conjectured that the majority (no less than half) of positive integers up to any finite limit \$\ge2\$ have an odd number of prime factors, counted with multiplicity. Mathematically, the summatory Liouville function \$L(n)\$ (A002819) was posited to satisfy the inequality $$ L(n)=\sum_{k=1}^n\lambda(k)\le0\ $$ for all \$n\ge2\$, wherein $$ \lambda(k)=(-1)^{\Omega(k)}=\begin{cases}-1,\ \text{$k$ has an odd number of prime factors}\\\phantom{-}1,\ \text{$k$ has an even number of prime factors}\end{cases} $$ is the Liouville function (A008836), related to the parity of the number of prime factors of \$k\$, and \$\Omega(k)\$ is the prime-factor-counting omega function that respects multiplicity.

The Pólya conjecture was shown to be false in 1958 when Brian Haselgrove proved the existence of an enormous counterexample near \$n=\exp(831.847)\approx1.845\times10^{361}\$. Subsequently, it has been shown that the smallest counterexample is \$n=906\,150\,257\$, and that the conjecture fails for most values of \$n\$ in the range \$906\,150\,257\le n \le 906\,488\,079\$. It is also now known that \$L(n)\$ changes sign infinitely often.

The code prints two values for each integer \$n\ge1\$: $$ \DeclareMathOperator{\sgn}{sgn} \begin{gather} \lambda(n), \tag{1} \\ \sgn\bigl[2L(n)-1\bigr]. \tag{2} \end{gather} $$ The first value is the \$n\$th term of A008836. The second value, chosen to avoid zeros in \$L(n)\$, is (arguably) more interesting. Given the results quoted above, we see that sequence \$(2)\$ alternates between \$-1\$ and \$1\$ infinitely often. However, of its first \$906\,150\,257\$ values, only two (the first and the last) are \$1\$; the intervening \$906\,150\,255\$ values are all \$-1\$.

Commented code

∞v             # iterate over all positive integers y
  ®            # push -1
   yÒ          # push list of prime factors of y (with duplicates)
     g         # length of this list; yields Ω(y)
      m        # exponentiate top two stack items; yields -1**Ω(y) = λ(y)
       =       # print λ(y), keeping it on the stack
        O      # sum the stack; yields L(y)
         x<    # push 2*L(y)-1, keeping L(y) on the stack
           .±, # print the sign
\$\endgroup\$
10
\$\begingroup\$

Wolfram Language (Mathematica)

primesUpTo[n_] := Select[Range[n], PrimeQ];
sumsOfTwoPrimes[n_] := Union @@ Outer[Plus, primesUpTo[n], primesUpTo[n]];
GoldbachConjectureHoldsFor[n_] := MemberQ[sumsOfTwoPrimes[n], n];
BooleanToSign[TrueOrFalse_] := 2 Boole[TrueOrFalse] - 1;

Do[Print[ BooleanToSign@GoldbachConjectureHoldsFor[2n] ], {n, ∞}]

Try it online!

  • primesUpTo generates a list of all primes up to n, and then sumsOfTwoPrimes generates all sums of two such primes.
  • This allows GoldbachConjectureHoldsFor to check whether n is the sum of two primes. (The function works for all n, though the Goldbach conjecture itself is concerned only with even n.)
  • GoldbachConjectureHoldsFor returns True or False, which BooleanToSign converts to 1 or -1 respectively.
  • Therefore BooleanToSign@GoldbachConjectureHoldsFor[2n] returns 1 if the Goldbach conjecture holds for 2n and -1 otherwise.
  • The Do[Print[ ... ], {n, ∞}] prints (in principle) the infinite list of results.

For those looking not to repeat earlier sequences, this sequence starts with a -1 and then contains only 1s forever thereafter ... or does it?!

\$\endgroup\$
10
\$\begingroup\$

Python 3, 84 bytes

s=b's=%r\nwhile[print(c%%2*2-1)for c in s%%s]:0'
while[print(c%2*2-1)for c in s%s]:0

Try it online!

Quine, which outputs 1 or -1 according to the last bit of each byte of the quine, repeating infinitely. Starts 1 1 -1 1 1 1 1 -1 -1 -1

Previously 107 91 bytes. I know it's not , but I couldn't resist golfing it a bit. This does change the sequence slightly but no other sequences are the same so it doesn't affect the competition

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

C (gcc), 38 bytes

int f() {
  return (rand() & 2) - 1;
}

Try it online!

This could be golfed into 21 bytes (f(n){n=(rand()&2)-1;}) but this question is not tagged as .

In C, random without seeds behave deterministically which actually fit the requirement of this question. I don't know how the sequence is generated. But it does generate a list which only contains 1's and -1's, some how.

First 100 generated values are:

 1  1 -1  1 -1  1  1 -1 -1 -1 
 1  1  1  1  1  1 -1  1 -1 -1 
 1 -1  1 -1  1  1  1  1  1  1 
-1  1  1  1 -1  1 -1 -1  1  1 
-1 -1 -1  1 -1 -1  1 -1  1  1 
-1  1  1 -1 -1 -1  1  1 -1 -1 
-1 -1 -1  1 -1 -1  1 -1 -1 -1 
-1  1  1 -1  1  1  1 -1  1  1 
 1 -1 -1  1 -1 -1  1  1  1  1 
-1 -1 -1 -1  1 -1  1  1  1  1 
\$\endgroup\$
0
4
\$\begingroup\$

Wolfram Language (Mathematica), 56 bytes

Outputs the sequence infinitely.
Returns 1 if n is a quadratic residue of p=nextPrime(n) and -1 if n is a quadratic nonresidue of p.
In number theory, an integer n is called a quadratic residue modulo p if it is congruent to a perfect square modulo p; i.e., if there exists an integer x such that:

\$ {\displaystyle x^{2}\equiv n{\pmod {p}}} \$

Otherwise, q is called a quadratic nonresidue modulo n.

Do[p=NextPrime[n,1];Print@Mod[n^((p-1)/2),p,-1],{n,∞}]

Try it online!

Let p be an odd prime and gcd(n,p)=1. Then n is a quadratic residue or nonresidue of p according to whether

\$ n^{\frac {p - 1} {2}} \equiv \text {1 (mod p) } \$ or \$ \text{ } n^{\frac {p - 1} {2}} \equiv \text {-1 (mod p)} \$

This is also known as the \$ \text {Legendre symbol (a/b)} \$ and the built-in Mathematica for this is:

JacobiSymbol[n,p]     

Here are the first 100.000 n acuumulated

enter image description here

\$\endgroup\$
4
  • \$\begingroup\$ Your definition of the Legendre symbol uses a where I think you meant to use n. \$\endgroup\$ Jun 2, 2021 at 2:58
  • \$\begingroup\$ @DanielOnMSE you are right, fixed! \$\endgroup\$
    – ZaMoC
    Jun 2, 2021 at 8:25
  • \$\begingroup\$ Would you be able to share your code for plotting the graph at the end? I'd be interested in doing something similar for my sequence. Much appreciated. \$\endgroup\$ Jun 3, 2021 at 1:41
  • 1
    \$\begingroup\$ @DanielOnMSE if your sequence is s={-1,-1,1,-1,1,1,1,-1,1...}, then just type ListPlot@Accumulate@s \$\endgroup\$
    – ZaMoC
    Jun 3, 2021 at 6:32
4
\$\begingroup\$

Ruby

When I saw this challenge I immediately thought of the "diagonal infinite proof thing", appearantly also known as Cantor's diagonal argument.

My idea was to

  1. reimplement each of the N previous sequences, in the order that they were submitted
  2. create a new sequence where each ith element differs from the ith element of the ith previous sequence.

So long as Cantor's diagonal argument is correct (it is), then this should create a new sequence which is different from all the previous sequences.

Starting off with some usefull helpers:

def sgn(n) = n >= 0 ? 1 : -1   # New Ruby 3 syntax
def flatten_binary(seq) = seq.map(&:to_s).flat_map(&:chars).map(&:to_i).map { sgn _1 - 1 }
z = 0.step.lazy
n = 1.step.lazy

Step 1 turned out to be a whole lot of work, espacially as a few of the other answers simply flew over my head. Therefore I've cheated a little bit: Luckily, almost every answer provided a link and/or some copypastable start of the prefix, so for 13 of the sequences I've just copied them over and hardcoded the N first elements directly. These are marked with TODO in the following piece of code.

To spice things up along the way , I've also tried to interpret each submission and give them their own appropriate names:

sequences = [
# caird coinheringaahing's tangent
  n.map { sgn Math.tan(_1) },
# user100177's lazy duo - TODO
  [1, -1, 1, 1 ,1, -1].cycle,
  [1, 1, -1, 1, -1, 1].cycle,
# Dingus's first non-trivial 05AB1E answer - TODO
  [1, 1, -1, -1, -1, -1, 1, -1, -1, -1, 1, -1, -1, -1, -1, -1, 1, -1, 1, -1, -1, -1, -1, -1, -1, -1, 1, -1, 1].cycle,
# Noodle9's zigzag
  [-1,1].cycle,
# ZaMoC's Rudin-Shapiro Sequence - TODO
  [1, 1, -1, 1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, -1, -1, -1, 1, 1, 1].cycle,
# user99151's unity
  [1].cycle,
# hakr14's undocumented string
  n.flat_map { |i| [-1] + [1]*i },
# Greg Martin's Goldbach conjecture - TODO
  [-1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1].cycle,
# pxeger's quine - TODO
  [1, 1, -1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1, -1, -1, -1, 1, 1, 1, -1, -1, -1].cycle,
# Command Master's infinite quad
  [1, -1, -1, -1].cycle,
# Xi'an's kempnerial
  n.map { _1.digits.include?(9) ? 1 : -1 },
# tsh's pseudo random numbers - TODO
  [1, 1, -1, 1, -1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, -1, 1, -1, 1, 1, 1, 1, 1].cycle,
# Command Master's bidecimals
  flatten_binary(Enumerator.produce(2) { _1.to_s(2).to_i }.lazy.drop(1)),
# ovs's gray codes - TODO
  [1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, -1, -1].cycle,
# Kaddath.
  "Kaddath".unpack('H*')[0].to_i(16).to_s(2).chars.map{ |c| sgn(c.to_i - 1)}.cycle,
# Zaelin Goodman's Harshad numbers - TODO
  [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, -1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, -1, 1, -1].cycle,
# mazzy's tripartite function
  z.map { sgn(_1 % 3 - 2) },
# Kevin Cruijssen's Kolakoski sequence - TODO
  [-1, 1, 1, -1, -1, 1, -1, 1, 1, -1, 1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1].cycle,
# ZaMoC's quadratic residue - TODO
  [-1, -1, -1, 1, -1, -1, -1, -1, 1, -1, -1, 1, 1, -1, 1, 1, 1, -1, -1, -1, -1, -1, 1, 1, 1, -1, -1, 1].cycle,
# SketchySketch's Liouville function - TODO
  [1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1, -1, -1, 1, 1, -1, 1, 1, 1, -1, -1, -1].cycle,
# bb94's blazin' prefix
  z.map { -sgn(420 <=> _1) },
# user100690's unoriginal solution
  n.flat_map { |i| [1]*i + [-1] },
# SjoerdPennings's quinvigintal alternation
  ([1]*25 + [-1]*25).cycle,
# Sheik Yerbouti's period
  "This is a unique sequence\0".bytes.lazy.cycle.map { _1 % 2 * 2 - 1 },
# elementiro's pie hole - TODO
  [1, -1, -1, 1, -1, -1, 1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, -1, 1, -1, 1, -1, -1, -1].cycle,
# DanielOnMSE's square-free semi-primes - TODO
  [-1, -1, -1, 1, -1, -1, -1, 1, -1, 1, -1, -1, -1, 1, -1, -1, -1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, -1].cycle,
]

Step two is pretty trivial:

sequences.cycle.each do |sequence|
  next_number = sequence.peek
  print "#{next_number * -1}, "

  # advance all to next position
  sequences.each(&:next)
end

Prints an infinite sequence starting with:

-1, 1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1, 1, -1, 1, -1, -1, -1, -1, -1, 1, -1, -1

Attempt This Online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is really cool. I like how this will theoretically produce a unique sequence, which is a requirement for the submission. Something that a fair few of us (myself included) omitted as it is no trivial matter to prove your sequence is different from all the others. \$\endgroup\$ May 11, 2022 at 1:54
3
\$\begingroup\$

Jelly, 8 bytes

‘ÆTṠṄaƲß

Try it online!

This outputs the series generated by \$f(n) = \text{sgn}(\tan(n+1))\$ as \$n = 0, 1, 2, 3, ...\$, separated by newlines. This only yields \$0\$ iff \$\tan(n+1) = 0\$, which only happens when \$n = 2k\pi-1\$ for some integer \$k\$. As this is only an integer when \$k = 0\$ and \$n = -1\$, this never happens.

How it works

‘ÆTṠṄaƲß - Main link. Takes an integer n (initially 0) on the left
‘        - Yield n+1
      Ʋ  - To n+1:
 ÆT      -   tan(n+1)
   Ṡ     -   sgn(tan(n+1))
    Ṅ    -   Print and return sgn(tan(n+1))
     a   -   Replace sgn(tan(n+1)) with n+1
       ß - Recursively call 
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 32 bytes

Do[Print@RudinShapiro@n,{n,∞}]

Try it online!

Rudin-Shapiro Sequence

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Note that "You may not take any input", so just a builtin function is invalid unless it outputs the infinite sequence when called. Changing it to be an infinite loop which calls the builtin each time is allowed \$\endgroup\$ Jan 2, 2021 at 21:54
  • \$\begingroup\$ @cairdcoinheringaahing fixed \$\endgroup\$
    – ZaMoC
    Jan 2, 2021 at 22:00
3
\$\begingroup\$

Bash, 5 bytes

This outputs all items in the sequence \$1, 1, 1, 1, ...\$ ... the rules do not explicitly forbid it.

yes 1

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ lmao, and it's true that the rules do not explicitly forbid it. \$\endgroup\$
    – LianSheng
    Jan 4, 2021 at 10:00
  • \$\begingroup\$ but it said: Be creative. Avoid simply outputting constant runs of 1s or −1s... \$\endgroup\$
    – LianSheng
    Jan 4, 2021 at 10:02
  • 2
    \$\begingroup\$ This answer is perfectly valid, if a bit uncreative @LianSheng. The "avoid outputting constant runs" was merely advice for how to get a higher score (more votes) \$\endgroup\$ Jan 4, 2021 at 16:38
3
\$\begingroup\$

Python 3

def gray(n):
  return n ^ n>>1

previous = n = 0
while True:
    n += 1
    bitcount = bin(gray(n)).count('1')
    print(bitcount - previous)
    previous = bitcount

Try it online!

Sequence starts with 1 1 -1 1 1 -1 -1 1 1 1 -1.

These are the differences in the number of set bits between adjacent gray codes. This happens to be the same sequence as:

  1. Start with a single 1
  2. Reverse the current sequence of 1 and -1 and negate every value. Join the original and modified sequence with a 1. Repeat step 2.

1 -> 1 1 -1 -> 1 1 -1 1 1 -1 -1 -> 1 1 -1 1 1 -1 -1 1 1 1 -1 -1 1 -1 -1 -> ...

Bonus implementation in Coconut using this construction:

sequence = [1]
print(1)
while True:
    new = sequence |> reversed |> map$(-) |> list |> x->[1]+x
    new |*> print$(sep='\n')
    sequence.extend(new)

Try it online!

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

JavaScript, 120 bytes

k=>{f=n=>{a=0;if(!(n-1))return 1;for(i=0;++i<n;)if(!(n%i))a += f(i);return 0.5<a?-1:1};for(i=0;++i<k;)console.log(f(i))}

Print the Liouville function \$f(n)\$ for every integer \$n\$, OEIS A008836.

Explain

The recurrence formula f(1)=1; n > 1: f(n) = sign(1/2 - Sum_{d<n, d|n} f(d)).

k=>{                                         // starts a function
  f=n=>{                                     // function for recurrence
    a=0;                                     // init accumulator
    if(!(n-1)) return 1;                     // end of recurrence
    for (i = 0; ++i<n;)                      // start loop, from 1 to n-1
      if(!(n%i)) a += f(i);                  // if n is divisible by i, add f(i) to a
    return 0.5<a?-1:1                      // return sign(1/2 - a)
  };
  for (i = 0; ++i<k;) console.log(f(i))      // print the sequence
}
\$\endgroup\$
2
\$\begingroup\$

Haskell, 55 bytes

a=1: -1:(zipWith(*)a$tail b)
b=1:1:(zipWith(*)b$tail a)

Try it online!

a is the infinite sequence here. Neither is very interesting - a is [1,-1,1,1,1,-1] repeated forever and b is [1,1,-1,1,-1,1] repeated forever. However, I think this shows how cool Haskell's laziness is: you have two infinite lists dependent on each other. a starts with 1 and -1, and the rest of it is found by multiplying a by the tail of b. Similarly, b starts with 1 and 1, and the rest of it is found by multiplying b by the tail of a.

So the third element of a would be 1 * 1 = 1 and for b it would be 1 * -1 = -1. The fourth elements would be -1 * -1 = 1 for a and 1 * 1 = 1 for b, and so on.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Would you mind making a definitive choice as to which of a and b is your sequence, so that it's easier for others to follow the "sequences must be unique" rule? \$\endgroup\$ Jan 2, 2021 at 20:36
  • \$\begingroup\$ Oh yeah, of course \$\endgroup\$
    – user100177
    Jan 2, 2021 at 20:36
2
\$\begingroup\$

Pyth, 10 bytes

#V=hZ_1VZ1

Try it online!


Sequence is -1,1,-1,1,1,-1,1,1,-1,1,1,1,-1,1,1,1,-1,1,1,1..., or (-1,(1)*n)*n for n in [1, ∞).

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

PHP, 127 bytes

$k = base_convert(unpack('H*', "Kaddath")[1], 16, 2);
for(;;$i = $i==strlen($k) ? 0 : $i){
  echo ($k[$i++] ? 1 : -1) . "\n";
}

Try it online!

It first converts the string "Kaddath" to a binary string ("1001011011000010110010001100100011000010111010001101000") then loops on the string to produce the repeated sequence by outputting 1 for each 1 and -1 for each 0

Nothing sensational I fear, just warming up for the new golfing year!

EDIT: clearer code formatting, some parts were golfed by habit

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

Wolfram Language (Mathematica), 256 bytes

Classifies every square-free semi-prime as a 1 or a -1.

f[n_]:=Return[SquareFreeQ[n]&&PrimeOmega[n]==2];
g[n_]:=Return[Map[First,FactorInteger[n]]];
h[{a_,b_}]:=Return[List[a*ModularInverse[a,b], b*ModularInverse[b,a]]];
i[{c_,d_}]:=Return[If[Max[{c,d}] == c,-1, 1]];
Do[If[f[n], Print@i[h[g[n]]], 0], {n,∞}]

Try it online!

First 10 terms

-1,-1,-1,1,-1,-1,-1,1,-1,1...

Which correspond to classification of the following square-free semi-primes:

6, 10, 14, 15, 21, 22, 26, 33, 34, 35...

Sequence definition:

Let \$n\$ be a Square-Free Semiprime, and let \$p\$ and \$q\$ be the two distinct prime numbers (positive) that uniquely produce \$n\$:

$$n = pq$$

It follows from Bezout's Identity that \$\exists a, b \in \mathbb{Z} \$ such that:

$$ap + bq = 1$$

Now, as both \$p\$ and \$q\$ are positive, it follows that \$a\$ and \$b\$ have opposite signs. Possible values for \$a\$ and \$b\$ can be given by the modular equations

$$ ap \equiv 1 \mod q $$

$$ bq \equiv 1 \mod p $$

Whereby choosing a representative for \$a\$ or \$b\$ enforces the choice for the representative of the other.

Let \$c\$ be the smallest positive representative of \$a\$'s equivalence class.

Similarly, let \$d\$ be the smallest positive representative of \$b\$'s equivalence class.

Thus, it follows that:

$$ cp + dq = 1 + n$$

Now we can decide on a binary classification of \$n\$ conditioned on the following:

$$cp > dq$$

Or in other words which prime number contributes the most to the sum: \$ cp + dq = 1 + n\$

As it is arbitrary, we let \$p < q\$ (One of the primes is always smaller than the other as they are not equal, otherwise \$n\$ would not be square-free), thus if \$cp > dq\$ we produce a \$-1\$, otherwise a \$1\$.

EXAMPLE

Consider the semi-prime \$n = 21\$ which is uniquely factorised by \$3\$ and \$7\$. By definition we assign the smaller prime to the variable \$p\$.

$$p = 3$$

$$q = 7$$

Now we can find infinitely many pairs of integers \$a\$ and \$b\$ such that:

$$ 3a + 7b = 1$$

These values can be found by the extended-Euclidiean algorithm (An algorithm used to solve modular equations like the ones listed previously). Let's find one of these pairs, specifically the one where \$a\$ and \$b\$ have the smallest magnitude. In this case it is easy to verify (and verbose to show via the extended-Euclidean algorithm) that the two such values are:

$$a = -2$$

$$b = 1$$

Now if we were to add \$n\$ to both sides of \$ap + bq = 1\$

We get:

$$pq + ap + bq = 1 + n$$

$$(q + a)p + bq = 1 + n$$

Thus we let \$c = q + a\$ and \$d = b\$

For the specific example this yields:

$$c = 5$$

$$d = 1$$

Resulting in:

$$5*3 + 1*7 = 1 + 21$$

\$3 < 7\$ and \$5*3 > 1*7\$ thus by definition we classify \$21\$ as a \$-1\$.

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

C (gcc), 14 bytes

n=1;f(){n=-n;}

Try it online!

Next value is returned every time \$f\$ is called.

First answer to repeat alternating signs: \${-1, 1, -1, 1 \dots}\$

\$\endgroup\$
3
  • \$\begingroup\$ I believe that you should put the for loop inside the function, or make it recursive. The function should output an infinite sequence. \$\endgroup\$
    – anotherOne
    Feb 12, 2021 at 10:21
  • \$\begingroup\$ @SheikYerbouti One of the OP's options for output is: Outputting the next value in the sequence each time your code is run. \$\endgroup\$
    – Noodle9
    Feb 12, 2021 at 12:07
  • \$\begingroup\$ Oh sorry, I missed that. \$\endgroup\$
    – anotherOne
    Feb 12, 2021 at 12:27
1
\$\begingroup\$

R, 33 bytes

Inspired from an earlier code-golf challenge, on the Kempner series, this R code print out 1 when integer contains the digit 9 and -1 otherwise:

while(T<-T+1)show(2*grepl(9,T)-1)

Try it online!

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

05AB1E

2[bxS<»,

Try it online!

Repeatedly converts a to binary, replaces 0 with -1 and then set the new a to a in binary interpreted in base-10, starting with a=2. EDIT: Turns out it is A008559

Explaination:

2              Pushes 2
 [             infinite loop
  b            convert to binary (e.g. "10")
   x           pushes tos and itself doubled.
               as strings is 05AB1E are numbers, 10 gets interpreted as a number         
               (e.g. 10, 20)
    S          converts the top of the stack to a string of characters (e.g. ["2", "0"])
     <         subtract 1, which vectorizes.
               because in 05AB1E strings are numbers, it subtract 1 from each of the digits
      »        join by newlines
       ,       print
\$\endgroup\$
1
\$\begingroup\$

PowerShell, 20 bytes

for(){2*!(++$x%3)-1}

Try it online!

1 for divisible by 3, -1 for other

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

PowerShell, 68 45 43 bytes

-an enormous 23 bytes thanks to Mazzy! The madlad.

Prints 1 when the integer is a Harshad number (it is divisible by the sum of it's own digits).

for(;){2*!(++$x%($x-replace'','+0'|iex))-1}

Try it online!

Link is to a longer version of the code that terminates after 1000 signs

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Try it online! :) \$\endgroup\$
    – mazzy
    Jan 6, 2021 at 7:01
  • 2
    \$\begingroup\$ @mazzy Wow, really goes to show how bollocks the popular quote Some people, when confronted with a problem, think “I know, I'll use regular expressions.” Now they have two problems. is. Very clever work, as usual! \$\endgroup\$ Jan 6, 2021 at 14:19
1
\$\begingroup\$

Java

My lambda functions below outputs the Kolakoski sequence (A000002), where the 1 and 2 are mapped to -1 and 1 respectively.

The Kolakoski sequence is a self-referential sequence which defines: \$a(n)\$ is the length of the \$n^{th}\$ run, starting at \$a(1)=1\$. Here a visual of the sequence, with the runs underneath it (both lines form the same exact sequence of 1s and 2s):

1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1 2 1 1 2 1 ...
— ——— ——— — — ——— — ——— ——— — ——— ——— — — ——— — —
1  2   2  1 1  2  1  2   2  1  2   2  1 1  2  1 1 ...

Which results in the following lambda function in Java:

import java.util.*;                       // Required import for List/ArrayList/Arrays
()->{                                     // Method without parameter nor return-type:
  List<Integer> sequence = new ArrayList(Arrays.asList(1,2,2));
                                          //  Start the sequence at 1,2,2
  for(int i=2;;i++){                      //  Loop `i` from 2 upwards indefinitely:
    int valueToPrint = sequence.get(i-2); //   Get the `i-2`'th value from the sequence
    System.out.print(valueToPrint*2-3     //   Convert 1 to -1 and 2 to 1, and print it
                      + " ");             //   with space delimiter
    int valueToAdd = i % 2 == 0 ?         //   If `i` is even:
                      1                   //    Create a value 1
                     :                    //   Else (`i` is odd instead):
                      2;                  //    Create a value 2
    sequence.add(valueToAdd);             //   Add that value to the sequence
    if(sequence.get(i) == 2)              //   And if the `i`'th value of the sequence is 2:
      sequence.add(valueToAdd); }}        //    Add that same value again

Try it online.

Golfed this would be 109 bytes:

v->{var s="122";for(int i=1;;s+=(s.charAt(i)>49?11:1)<<i%2)System.out.print((s.charAt(++i-2)-48)*2-3+" ");}

Try it online.

Explanation:

v->{                       // Method with empty unused parameter and no return-type
  var s="122";             //  Sequence-String, starting at 1,2,2
  for(int i=1;             //  Loop from `i` upwards indefinitely:
      ;                    //    After every iteration:
       s+=                 //     Append to the sequence-String:
          (s.charAt(i)>49? //      If the `i`'th digit is a 2:
            11             //       Use 11
           :               //      Else (the `i`'th digit is a 1 instead)
            1)             //       Use a 1
              <<i%2)       //      And bitwise left-shift it by `i` modulo-2
                           //      (1 and 11 are 1 and 1011 in binary respectively.
                           //       Left-shifting this by 0 for even `i` won't change them,
                           //       but left-shifting them by 1 for odd `i` would become
                           //       binary 10 and 10110, which are the integers 2 and 22)
    System.out.print(      //   Print:
      (s.charAt(++i-2)     //    The `i-2`'th character
                           //    (after we've first increased `i` by 1 with `++i`)
       -48)                //    converted from character to integer
           *2-3            //    and transformed from 1/2 to -1/1 respectively
       +" ");}             //    Appended with a space delimiter
\$\endgroup\$
1
\$\begingroup\$

Raku

(|(1 xx 420), -1, |(1 xx *))

Returns -1 for the 421st element and 1 elsewhere.

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

JavaScript - 92 bytes

x=[];for(i=1;i<Infinity;i++){x.push(...new Array(i).fill("1"));x.push("-1")};console.log(x);

Not the most original solution, but the shortest JavaScript one to date... The array we end up with will never actually be printed, but if you replace Infinity with something else like 10, you can see the pattern. The i-th iteration of the infinite loop adds i 1s to the array then adds a -1.

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

BRASCA, 23 bytes

1[25S[1n{]x25S[01-n{]x]

Try it online!

Outputs 25 1's, then 25 -1's, then repeats.

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

C (gcc), 111 bytes

int i;

int main( void ){

    printf("%d ", "This is a unique sequence"[i++ % 26] % 2 * 2 - 1);

    main();
}

Try it online!

The program prints the following sequence periodically

-1 -1 1 1 -1 1 1 -1 1 -1 1 -1 1 1 1 1 -1 1 1 1 1 1 -1 1 1 -1

Here it becomes evident

Any bonus point for being 111 bytes?

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

Pyt, 17 bytes

1`ĐĐĐŚ⇹ąŁ+|2*⁻ƥ⁺ł

Try it online!

Starting at n=1, outputs 1 if n is divisible by the sum of its digits PLUS its length when written in base 10, otherwise outputs -1.

Sequence begins: [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,-1,1,-1,-1,-1,1]

1                       push 1
 `              ł       do... while top of stack is truthy
  ĐĐĐ                   Đuplicate three times
     Ś                  digit Śum
      ⇹                 swap top two items on stack
       ąŁ               convert to ąrray of digits; get Łength
         +              add
          |             does the sum divide n?
           2*⁻          coerce boolean to integer, double and decrement
              ƥ         ƥrint
               ⁺        increment

It is different from all of the previous sequences:

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

05AB1E, 4 bytes

₄Þ·<

Try it online!

Prints [1, -1, -1, -1] repeated forever

₄ push 1000
Þ repeat infinitly - [1, 0, 0, 0, 1, 0, 0, 0, ...]
· double - [2, 0, 0, 0, 2, 0, 0, 0, ...]
< substract 1 - [1, -1, -1, -1, 1, -1, -1, -1, ...]
\$\endgroup\$
0
\$\begingroup\$

MATLAB/Octave

SymbPi = sym(pi);
detail = sym(1);
while 1
    bool = isAlways(mod(SymbPi,2*detail) > detail);
    if bool
       fprintf('1,');
    else
       fprintf('-1,');
    end
    detail = detail / 2;
end

Try it online! In theory can work forever but at some point it raches maximal precision.

Utilizes π number. In each loop iteration it calculates remainder from division by 2*detail and checks whether its bigger than detail. detail is halved each iteration so it's: 1, 0.5, 0.25, 0.125, 0.0625 ... We're basically converting π to binary form. And for each so calculated boolean if it's true we print 1, if not -1,.
Also, I used fprintf instead of classic disp just so everything will be nicely in one line.

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