27
\$\begingroup\$

The van der Corput sequence is one of the simplest example of low-discrepancy sequence. Its n-th term is just 0.(n written in base 10 and mirrored), so its first terms are :

0.1, 0.2,0.3,0.4, 0.5,0.6,0.7, 0.8,0.9, 0.01, 0.11,0.21,0.31, 0.41,0.51,0.61, 0.71,0.81,0.91, 0.02, 0.12,0.22,0.32, 0.42,0.52,0.62, 0.72,0.82,0.92, ...

The challenge

Write a program or a function in any programming language that takes as input a positive integer n less than 10^6 and returns or print the first n terms of the van der Corput sequence. The output format can be a list of floating point numbers, a list of strings of the form 0.digits, or a unique string where the terms are separated by commas and/or whitespaces, newlines.

Standard loopholes are forbidden. The shortest source code wins.

\$\endgroup\$

35 Answers 35

16
\$\begingroup\$

05AB1E, 6 bytes

Code:

>GNÞR,

Try it online!

Explanation:

>       # Increment, pushes input + 1
 G      # For N in range(1, input + 1):
  N     # Push N
   Þ    # Convert to double, which appends `.0` at the end of an integer
    R   # Reverse top of the stack
     ,  # Pop and print with a newline

Uses CP-1252 encoding.

\$\endgroup\$
  • \$\begingroup\$ You mean, windows-1252? \$\endgroup\$ – Ismael Miguel Feb 10 '16 at 12:50
  • \$\begingroup\$ @IsmaelMiguel That is the same \$\endgroup\$ – Adnan Feb 10 '16 at 13:13
  • \$\begingroup\$ I know, but it usually isn't recognized by the name CP-1252 \$\endgroup\$ – Ismael Miguel Feb 10 '16 at 13:24
  • \$\begingroup\$ Did you have to modify your language for the purpose of this challenge? \$\endgroup\$ – Andrew Savinykh Feb 10 '16 at 20:50
  • \$\begingroup\$ @AndrewSavinykh No, that is considered cheating and is not allowed on this site. It works with version 7.3, which was released before this challenge was posted. \$\endgroup\$ – Adnan Feb 10 '16 at 20:55
8
\$\begingroup\$

Oracle SQL 11.2, 64 62 58 bytes

SELECT REVERSE(LEVEL||'.0')FROM DUAL CONNECT BY LEVEL<=:1;

Old version

SELECT '0.'||REVERSE(TRIM(LEVEL))FROM DUAL CONNECT BY LEVEL<=:1;

Concatenating '' to a number casts it to a string. It is 2 bytes shorter than using TRIM(), which is shorter than TO_CHAR().

Since concatenating a string to a NUMBER results in a string, it is possible to use that string to manage the '0.' part of the result.

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

CJam, 14 11 bytes

Thanks to Sp3000 for saving 3 bytes.

ri{)d`W%S}/

Test it here.

Explanation

ri     e# Read input and convert to integer N.
{      e# For each i from 0 to N-1...
  )    e#   Increment.
  d    e#   Convert to double.
  `    e#   Get string representation (which ends in ".0").
  W%   e#   Reverse.
  S    e#   Push a space.
}/
\$\endgroup\$
7
\$\begingroup\$

Perl 6, 24 22 20 bytes

{"0."X~(^$_)».flip}

Thanks Aleks-Daniel Jakimenko-A. for yet another two bytes

old version

{("0."~.flip for ^$_)}
# Alternate below, same byte count
{map ^$_: "0."~*.flip}

EDIT: Thanks raiph for extra 2 bytes

usage

> my &f = {"0."X~(^$_)».flip}
-> ;; $_? is raw { #`(Block|333498568) ... }
> f(25)
(0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.01 0.11 0.21 0.31 0.41 0.51 0.61 0.71 0.81 0.91 0.02 0.12 0.22 0.32 0.42)
\$\endgroup\$
  • 1
    \$\begingroup\$ {("0."~.flip for ^$_)} saves 2 bytes \$\endgroup\$ – raiph Feb 10 '16 at 6:44
6
\$\begingroup\$

Mathematica, 40 bytes

"0."<>StringReverse@ToString@#&~Array~#&

Test case

%[20]
(* {0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,0.01,0.11,0.21,0.31,0.41,0.51,0.61,0.71,0.81,0.91,0.02} *)
\$\endgroup\$
5
\$\begingroup\$

Pyth, 8 bytes

m_`cd1SQ

Try it online.

This is really just a combination of this and this answer. Therefore I'm making it a community wiki.

\$\endgroup\$
4
\$\begingroup\$

Pyth, 11 bytes

m+"0."_`dSQ

Try it here!

Explanation

m+"0."_`dSQ  # Q = input

m        SQ  # Map the range(1,Q) to...
 +           # ...the concatenation of:
  "0."_`d    # "0." and the reversed element
\$\endgroup\$
4
\$\begingroup\$

Pyth - 10 bytes

_M+R".0"SQ

Try it online here.

\$\endgroup\$
  • \$\begingroup\$ One byte smaller if you do VSQ... \$\endgroup\$ – Jakube Feb 9 '16 at 15:52
4
\$\begingroup\$

JavaScript (ES6), 58

An anonymous function returning a string with comma separated values

n=>[...[...Array(n)].map(_=>n--+'.0')+''].reverse().join``

TEST

f=n=>[...[...Array(n)].map(_=>n--+'.0')+''].reverse().join``

function test() { R.textContent = f(+I.value) }

test()
N:<input id=I type=number value=20 oninput="test()"><br><pre id=R></pre>

\$\endgroup\$
4
\$\begingroup\$

MATL, 10 bytes

:"'0.'@VPh

Try it online!

:          % implicit input. Generate vector [1,2,...,input]
"          % for each
  '0.'     %   push string '0.'
  @        %   push loop variable (that is, 1,2,3,... in each iteration)
  V        %   convert to string
  P        %   reverse
  h        %   concatenate horizontally
           % implicit end of loop
           % implicit display of all stack contents
\$\endgroup\$
4
\$\begingroup\$

Haskell, 36, 27 bytes

f n=reverse.show<$>[1.0..n]

Two bytes saved by nimi and an additional 7 by Lynn.

\$\endgroup\$
  • \$\begingroup\$ f n=reverse.show<$>[1.0..n] \$\endgroup\$ – Lynn Feb 11 '16 at 18:56
3
\$\begingroup\$

Brachylog, 23 bytes

:0re:""rcr:"0."rcw,@Sw\

This takes a number as input and outputs the result to STDOUT, separated by spaces.

Fairly straightforward. Unfortunately we have to concatenate the number with an empty string to convert this number to a string (:""rc), because there is no built-in conversion predicate yet.

The conversion to string is necessary, because if we reverse the digits of the number, then the leading zeros (e.g. 10 becomes 01) would be lost.

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

PowerShell, 52 bytes

while($a++-$args[0]){"0."+-join"$a"["$a".Length..0]}

A little longer than I'd like, but uses a couple of neat tricks.

The while loop is obvious, but the conditional is a little tricky - we have $a (which starts as $null when first referenced) and then subtract our input number $args[0]. In PowerShell, math operations on $null treat it as zero, so for input 20 for example this will result in -20. Since any non-zero number is $true, the loop conditional will be $true right up until $a equals our input number (at which point the subtraction will equal 0 or $false). The trick comes from the post-increment ++, which doesn't execute until after the subtraction is calculated, so handling input of 1 will correctly output 0.1 and then stop the loop on the next iteration.

Each time in the loop, we just create a string literal which gets left on the pipeline and output accordingly. We construct this from "0." concatenated with the result of the unary -join operator that has acted on the char-array created from taking the string "$a" backwards (by indexing via the range "$a".length..0).

Test Runs

PS C:\Tools\Scripts\golfing> .\van-der-corput-sequence.ps1 1
0.1

PS C:\Tools\Scripts\golfing> .\van-der-corput-sequence.ps1 20
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.01
0.11
0.21
0.31
0.41
0.51
0.61
0.71
0.81
0.91
0.02
\$\endgroup\$
3
\$\begingroup\$

Bash, 36 bytes

for i in `seq $1`;do rev<<<$i.0;done

Takes a number as a command line argument, and outputs each term on a separate line. For example:

$ ./vdc.sh 12
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.01
0.11
0.21
\$\endgroup\$
  • 2
    \$\begingroup\$ If not pure Bash anyway: seq -f%g.0 $1|rev. \$\endgroup\$ – manatwork Feb 25 '16 at 10:23
  • \$\begingroup\$ @manatwork Cool. I didn't know seq could do formatted output. \$\endgroup\$ – squeamish ossifrage Feb 25 '16 at 10:38
3
\$\begingroup\$

Japt, 12 bytes

Uò1 ®+".0" w

Test it online!

How it works

           // Implicit: U = input integer
Uò1 ®      // Create the inclusive range [1..U], and map each item Z to:
+".0" w    //  Z + ".0", reversed.
           // Implicit: output last expression
\$\endgroup\$
3
\$\begingroup\$

beeswax, 57 53 bytes

Working on the binary digit output problem for rosettacode I noticed that I could use the same short division algorithm for the van der Corput sequence, just using division and modulo by 10 instead of 2. The output is reversed in both cases.

Golfed down by 4 bytes, by mirroring the code:

`.0` XfE@~@L#;
 { %X<#dP@T~P9_
   q<#   N
    >:'bg?b

Hexagonal prettyprint, for easier orientation:

` . 0 `   X f E @ ~ @ L # ;
 {   % X < # d P @ T ~ P 9 _
    q < #       N
     > : ' b g ? b

Explanation of one cycle through the program, using the original code:

;#L@~@EfX `0.`
_9P~T@Pb#>X% {
      N   #>p
      d?gd':<


                                                  lstack   gstack
                                _9P              [0,0,10]•         create bee, set top to 10
                                   ~T            [0,10,n]•         flip top and 2nd, enter n
                                     @P          [n,10,1]•         flip top and 3rd, increment top
                                       b                           redirect to upper left
                     [n,10,1]•        E          [n,10,1]•      (2)clone bee in horizontal direction
flip lstack 1st/3rd  [1,10,n]•       @ f         [n,10,1]•  [1]•   push lstack top on gstack       
flip lstack 1st/2nd  [1,n,10]•       ~   X                         clone bee in all directions
flip 1st/3rd         [10,n,1]•      @     `0.`                     print "0." to STDOUT
skip if 1st>2nd      [10,n,1]•     L      >                     (1)redirect 
if 1st<2nd, del. bee              #        X                       clone bee in all directions
(if 1st>2nd, terminate program)  ;          % {  [n,10,1]•         1st=1st%2nd, output lstack 1st to STDOUT
                                            >p                     redirect
                                             <                     redirect
                                            :    [n,10,0]•         1st=1st/2nd
                                           '                       skip next instr. if 1st=0
                                          d                        redirect to upper right, loop back to (1)
                                         g       [n,10,1]   [1]•   push gstack top on lstack 1st
                                       d?                   []•    pop gstack, redirect to upper right
                                       N                           print newline to STDOUT
                                       P         [n,10,2]          increment lstack 1st
                                       E                           looped back to (2)

Example:

julia> beeswax("vandercorput.bswx",0,0.0,Int(20000))
i300
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.01
0.11
0.21
0.31
0.41
  .
  .
  .
0.492
0.592
0.692
0.792
0.892
0.992
0.003

Program finished!
\$\endgroup\$
2
\$\begingroup\$

R, 59 Bytes

example(strsplit);cat(strReverse(sprintf('%s.0',1:scan())))

explanation

example(strsplit) creates the function strReverse (then it should be obvious)

Using IRanges::reverse, this could be golfed to 47 bytes

cat(IRanges::reverse(sprintf('%s.0',1:scan())))
\$\endgroup\$
2
\$\begingroup\$

Python 3, 47 bytes

lambda n:['0.'+str(i+1)[::-1]for i in range(n)]

a shorter solution with Python 2

lambda n:['0.'+`i+1`[::-1]for i in range(n)]

Test case

>>> f(25)
['0.1', '0.2', '0.3', '0.4', '0.5', '0.6', '0.7', '0.8', '0.9', '0.01', '0.11', '0.21', '0.31', '0.41', '0.51', '0.61', '0.71', '0.81', '0.91', '0.02', '0.12', '0.22', '0.32', '0.42', '0.52']
\$\endgroup\$
  • \$\begingroup\$ My Python solution was the same, but I think that f= is not required, so it is 47 bytes long. \$\endgroup\$ – Bob Feb 9 '16 at 13:58
  • \$\begingroup\$ @Bob ok i removed it \$\endgroup\$ – Erwan Feb 9 '16 at 14:12
  • \$\begingroup\$ This outputs the first n-1 terms. \$\endgroup\$ – seequ Feb 25 '16 at 14:09
  • \$\begingroup\$ @Seeq you are right i change the solution, it doesn't change the bytes count \$\endgroup\$ – Erwan Feb 25 '16 at 14:46
  • \$\begingroup\$ lambda n:['0.'+`i+1`[::-1]for i in range(n)] is shorter if you use Python 2. Also, you shouldn't say "Python 3.5" unless it requires 3.5, which it doesn't. This version requires Python 2. \$\endgroup\$ – mbomb007 Feb 25 '16 at 15:15
1
\$\begingroup\$

𝔼𝕊𝕄𝕚𝕟, 12 chars / 15 bytes

⩤⁽1ï⒨ß)Ė⍞.0ᴙ

Try it here (Firefox only).

It's... okay.

Explanation

⩤⁽1ï⒨ creates a range [1,ï] to map over, ß) converts mapitem (number) to string, Ė⍞.0 concats .0 to the end, and reverses the whole string.

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

Python 2, 54 Bytes

def f(i):
    for i in range(1,i):print("."+str(i)[::-1])

Explanation:

Iterate through the set [1,input) and appends the reversed i to ..

Still an be golfed more.

\$\endgroup\$
  • \$\begingroup\$ Use `i` instead of str(i). Also, I think you need to print the leading zero. \$\endgroup\$ – mbomb007 Feb 25 '16 at 15:17
1
\$\begingroup\$

PHP, 45 41 bytes

for(;$i++<$argv[1];)echo strrev(",$i.0");

Takes the input argument from CLI. Run like this:

php -r 'for(;$i++<$argv[1];)echo strrev(",$i.0");' 100
  • Saved 3 bytes by concatenating the string before reversing
\$\endgroup\$
1
\$\begingroup\$

Retina, 39 bytes

1
1$`0. 
(1)+
$#1
+`(\d)0\.(\d*)
0.$2$1

Takes input in unary.

Try it online here.

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

Gema, 45 characters

*=@set{i;0}@repeat{*;@incr{i}0.@reverse{$i} }

Sample run:

bash-4.3$ gema '*=@set{i;0}@repeat{*;@incr{i}0.@reverse{$i} }' <<< 12
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.01 0.11 0.21 
\$\endgroup\$
1
\$\begingroup\$

Julia, 50 38 33 31 bytes

I went for a different output format to shorten the code by 12 bytes. The function returns an array of strings now. Shortened by 5 more bytes. Thanks to Alex A. for reminding me of string interpolation and using an anonymous function (getting rid of 2 more bytes).

n->["0."reverse("$i")for i=1:n]

or alternatively

n->[reverse("$(i/1)")for i=1:n]

Test

julia> @time f(10000)
  0.002260 seconds (60.01 k allocations: 2.823 MB)
10000-element Array{ASCIIString,1}:
 "0.1"
 "0.2"
 "0.3"
 "0.4"
 "0.5"
 "0.6"
 "0.7"
 "0.8"
 "0.9"
 "0.01"
 "0.11"
 "0.21"
 "0.31"
 "0.41"
 "0.51"
 "0.61"
 "0.71"
 "0.81"
 "0.91"
 "0.02"
 "0.12"
 "0.22"
 "0.32"
 ⋮
 "0.8799"
 "0.9799"
 "0.0899"
 "0.1899"
 "0.2899"
 "0.3899"
 "0.4899"
 "0.5899"
 "0.6899"
 "0.7899"
 "0.8899"
 "0.9899"
 "0.0999"
 "0.1999"
 "0.2999"
 "0.3999"
 "0.4999"
 "0.5999"
 "0.6999"
 "0.7999"
 "0.8999"
 "0.9999"
 "0.00001"
\$\endgroup\$
  • 1
    \$\begingroup\$ 31 bytes: n->["0."reverse("$i")for i=1:n] \$\endgroup\$ – Alex A. Feb 10 '16 at 3:57
  • 1
    \$\begingroup\$ By the way, you can request that your profile be merged with the old one here. \$\endgroup\$ – Alex A. Feb 10 '16 at 4:02
  • \$\begingroup\$ Very cool, didn’t know that. Thanks! \$\endgroup\$ – M L Feb 10 '16 at 4:11
  • \$\begingroup\$ @AlexA. the anonymous function itself does not output anything. Wouldn’t a longer version like map(n->["0."reverse("$i")for i=1:n],3) (for n=3) be necessary to produce any output? That would make it (at least) as long as my solution. \$\endgroup\$ – M L Feb 11 '16 at 13:12
  • 1
    \$\begingroup\$ For an anonymous function, you just add the stipulation that to call it, one must assign it to a variable. Saves two bytes over a named function and is in compliance with our rules. \$\endgroup\$ – Alex A. Feb 11 '16 at 18:07
1
\$\begingroup\$

Python 2, 40 bytes

lambda n:[`i+1.`[::-1]for i in range(n)]

Example:

>>> f=lambda n:[`i+1.`[::-1]for i in range(n)]
>>> f(30)
['0.1', '0.2', '0.3', '0.4', '0.5', '0.6', '0.7', '0.8', '0.9', '0.01', '0.11', '0.21', '0.31', '0.41', '0.51', '0.61', '0.71', '0.81', '0.91', '0.02', '0.12', '0.22', '0.32', '0.42', '0.52', '0.62', '0.72', '0.82', '0.92', '0.03']

Algebraic solving:

corput(x) = reversed(str(float(x+1)))
          = reversed(str(x+1.))
          = str(x+1.)[::-1]
          = `x+1.`[::-1]
\$\endgroup\$
1
\$\begingroup\$

jq 1.5, 40 35 characters

(34 characters code + 1 character command line option.)

range(.)|"\(.+1).0"/""|reverse|add

Sample run:

bash-4.3$ jq -r 'range(.)|"\(.+1).0"/""|reverse|add' <<< 12
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.01
0.11
0.21

On-line test (Passing -r through URL is not supported – check Raw Output yourself.)

The same with links to documentation:

range(.) | "\(. + 1).0" / "" | reverse | add

As a more readable alternative, the above could be also written like this (on-line):

range(.) | . + 1 | tostring | . + ".0" | split("") | reverse | join("")
\$\endgroup\$
  • \$\begingroup\$ jq is really cool. Mind explaining how "\(.+1).0"/"" works? \$\endgroup\$ – seequ Feb 25 '16 at 19:50
  • \$\begingroup\$ There is nothing special, just a string interpolation \(…) and a division /, which in case of strings is split. \$\endgroup\$ – manatwork Feb 26 '16 at 7:01
1
\$\begingroup\$

BBC BASIC, 89 88 87 bytes

0T=1:REP.P."0."FNR(STR$T):T=T+1:U.0
1DEFFNR(S$)IFS$="":=""EL.=FNR(MI.S$,2))+LE.S$,1)

Used abbreviations to shorten things as much as possible. Compatible with both Brandy Basic and BASIC 2 on the original machine.

For modern BBC BASICs you could also leave off the line numbers to save two more bytes.

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

Dyalog APL, 12 bytes

{'0.',⌽⍕⍵}¨⍳

Try it online!

Straight-forward: the function { string '0.' before , the reversed string-representation of the argument to the function } for each ¨ of the numbers 1 through n .

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

JS, 66

T=101; // set T to the number of iterations wanted
for(o=[],i=0;i<T;i++)o[i]="0."+(""+i).split("").reverse().join("") // 66b

Output is the array called "o"

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

Groovy, 36 characters

{(1..it).collect{"$it.0".reverse()}}

Sample run:

groovy:000> ({(1..it).collect{"$it.0".reverse()}})(12)
===> [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.01, 0.11, 0.21]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.