28
\$\begingroup\$

Intro

Something I've played around with in recreational mathematics has been construction of a divisor table to visually compare/contrast the prime divisors of a set of numbers. The set of input numbers are across the top as column labels, the prime divisors are on the left as row labels, and a mark indicates where the two line up.

For example, for input 6, 9, 14, 22 a table similar to the following would be constructed:

    6  9 14 22
 2  *     *  *
 3  *  *
 7        *
11           *

This is because 6 has prime divisors of 2 and 3, 9 has prime divisors of 3, and so on.

Construction

  • The table is constructed such that the input numbers form column labels that are separated by spaces and in ascending order (you can assume they are pre-sorted), and the prime divisors are listed on the left in ascending order one per line forming the row labels.
  • Note that leading spaces on the prime divisors and input numbers may be required if the numbers are different lengths, so that all columns are the same width and line up appropriately.
  • Each divisor is represented by a single * (or other suitable ASCII character of your choosing, so long as the same character is used for all occurrences).
  • Multiple divisors are ignored (e.g., 3 x 3 = 9 but there's only one * for that intersection).
  • The * can be placed anywhere horizontally in the column, so long as it's unambiguous (I have all my examples with the * right-aligned).

Input

  • A list of positive integers in any convenient format, each >1.
  • You can assume that the input is pre-sorted.
  • The input is guaranteed to have only unique values.

Output

The resulting ASCII art representation of the prime divisor table.

Rules

  • Leading or trailing newlines or whitespace are all optional, so long as the characters themselves line up correctly.
  • If it's shorter to have a divider line separating the column/row headings from the tabular data, that's allowed, too.
  • Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
  • If possible, please include a link to an online testing environment so people can try out your code!
  • Standard loopholes are forbidden.
  • This is so all usual golfing rules apply, and the shortest code (in bytes) wins.

Examples

6,9,14,22

    6  9 14 22
 2  *     *  *
 3  *  *
 7        *
11           *


2,3,5,7

  2 3 5 7
2 *
3   *
5     *
7       *

2,4,8,16,32

   2  4  8 16 32
2  *  *  *  *  *

75,99,151,153

     75  99 151 153
  3   *   *       *
  5   *
 11       *
 17               *
151           *
\$\endgroup\$
  • 1
    \$\begingroup\$ Can we have divider lines after the top row and the left column? \$\endgroup\$ – ngenisis Feb 8 '17 at 22:28
  • \$\begingroup\$ @ngenisis Sure, I'll allow that. The exact formulation of the table is pretty open, since that's not the exact thrust of this challenge. \$\endgroup\$ – AdmBorkBork Feb 9 '17 at 13:21

12 Answers 12

5
\$\begingroup\$

Mathematica, 101 90 bytes

Thanks to ngenisis for saving 11 bytes!

TableForm[Outer[If[#∣#2,Y,""]&,f=#&@@@FactorInteger[1##],g={##}],TableHeadings->‌{f,g}]&

The character about a third of the way through is U+2223 (3 bytes). Unnamed function of a variable number of arguments, each of which is a nonzero integer, which returns a TableForm object (formatted output) like so:

TableForm output

f=#&@@@FactorInteger[1##] defines f to be the set of all primes dividing any of the inputs (equivalently, dividing their product 1##), while g is the list consisting of the inputs. Outer[If[#∣#2,Y,""]&,f,g] makes a table of Ys and empty strings corresponding to divisibility (we use the undefined token Y instead of a string "Y" or "*" to save two bytes). Then we use TableForm[...,TableHeadings->‌{f,g}] to format the resulting array with appropriate row and column headings.

Previous submission:

Grid[p=Prepend;Thread[q[Outer[If[#∣#2,Y,""]&,f=#&@@@FactorInteger[1##],g={##}]~p~g,f~p~""]]/.q->p]&
\$\endgroup\$
  • \$\begingroup\$ You can leave out the first "". \$\endgroup\$ – Martin Ender Feb 8 '17 at 22:26
  • 2
    \$\begingroup\$ TableForm[Outer[If[#∣#2,Y,""]&,f=#&@@@FactorInteger[1##],g={##}],TableHeadings->{f,g}]& if dividers are allowed \$\endgroup\$ – ngenisis Feb 8 '17 at 22:27
  • \$\begingroup\$ And the second as well if you change it to p[f,]. \$\endgroup\$ – Martin Ender Feb 8 '17 at 22:27
  • \$\begingroup\$ Grid lines to separate the headers is allowed. \$\endgroup\$ – AdmBorkBork Feb 9 '17 at 13:21
  • 1
    \$\begingroup\$ TableForm is cool, hopefully that will stay in my toolbox! \$\endgroup\$ – Greg Martin Feb 9 '17 at 18:22
3
\$\begingroup\$

Jelly, 18 bytes

PÆfQ0;ðḍ€+W}⁸;"o⁶G

Uses 1 instead of *, as allowed by the rules.

Try it online!

How it works

PÆfQ0;ðḍ€+W}⁸;"o⁶G  Main link. Argument: A (array of integers greater than 1)

P                   Take the product of the integers in A.
 Æf                 Compute all prime factors (with multiplicity) of the product.
   Q                Unique; deduplicate the prime factors.
    0;              Prepend a 0. Let's call the result P.
      ð             Begin a new, dyadic chain. Left argument: P. Right argument: A
       ḍ€           Divisible each; for each p in P, test all integers in A for
                    divisibility by P. Yields one row of the shape of A for each p.
                    Note that the first element of P is 0, so the first row of the
                    resulting matrix contains only zeroes.
          W}        Wrap right; yield [A].
         +          Add the results to both sides. Because of how Jelly's auto-
                    vectorization works, this adds the first row of [A] (just A) to
                    the first row of the divisibility matrix (all zeroes) and
                    leaves the other rows untouched.
            ⁸;"     Prepend the elements of P to the corresponding rows of the
                    previous result.
               o⁶   OR space; replace all zeroes with spaces.
                 G  Grid; format the matrix as requested in the challenge spec.
\$\endgroup\$
2
\$\begingroup\$

Jelly, 25 23 bytes

PÆfQ©ḍþµị⁾* ³;"Z⁶;®¤;"G

Try it online!

How?

It may well be shorter to use ÆE and filter out empty rows.

PÆfQ©ḍþµị⁾* ³;"Z⁶;®¤;"G - Main link: list of numbers, L
       µ                - monadic chain separation
P                       - product of L - multiply them all together
 Æf                     - prime factors (with repetitions, in ascending order)
   Q                    - unique items, maintaining order
                              - note that the product was performed to keep order
    ©                   - place in the register for later use, and yield
      þ                   - form the outer product of that and L using the dyad:
     ḍ                  -     isDivisor - 1 if divides, 0 if not
        ị⁾* <space      - index into "* " (1s to "*", 0s to " ")
            ³           - program's first input, L
             ;"         - zip with concatenation (column headers to the left)
               Z        - transpose (get it around the right way)
                   ¤    - nilad followed by link(s) as a nilad
                ⁶;®     - space (⁶) concatenated with (;) the register value (®)
                    ;"  - zip with concatenation (row labels to the left)
                      G - format the result as a grid (join items with spaces and
                                               rows with line feeds so they align)
                        - implicit print
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 264 260 ... 179 173 bytes

a=>[for(c of s=' '.repeat(w=a.slice(-1),i=0))if(!+(r=[i++?i:s,...i<2?a:a.map(x=>x%i&&c)].map(y=>(s+y).slice(-(w+1).length),a=a.map(d=x=>i<2|x%i?x:d(x/i))).join``))r].join`
`

I think this approach has now permanently exceeded the recursive one (currently 178 bytes):

f=(a,i=0,w=a.slice(-1))=>i++-w?(+(r=[i<2?'':i,...i<2?a:a.map(x=>x%i&&' ')].map(y=>(' '.repeat(w)+y).slice(-(w+1).length)).join``)?'':r+`
`)+f(a.map(d=x=>i<2|x%i?x:d(x/i)),i,w):''

Uses 0 in place of *, which is allowed by the challenge.

Test snippet

let g =

a=>[for(c of s=' '.repeat(w=a.slice(-1),i=0))if(!+(r=[i++?i:s,...i<2?a:a.map(x=>x%i&&c)].map(y=>(s+y).slice(-(w+1).length),a=a.map(d=x=>i<2|x%i?x:d(x/i))).join``))r].join`
`

console.log(g([6,9,14,22]))
console.log(g([2,3,5,7]))
console.log(g([2,4,8,16,32]))
console.log(g([75,99,151,153]))

\$\endgroup\$
  • \$\begingroup\$ If I'm not mistaken, you can use the | operator in the if statement, since you're comparing 2 booleans... \$\endgroup\$ – Luke Feb 9 '17 at 22:41
  • \$\begingroup\$ @Luke Hey, you're right. Not sure how I missed that \$\endgroup\$ – ETHproductions Feb 9 '17 at 22:59
  • \$\begingroup\$ Isn't it shorter to move the i<2 check inside the .map function? \$\endgroup\$ – Luke Feb 10 '17 at 7:02
  • \$\begingroup\$ @Luke If you mean change ...i<2?a:a.map(x=>x%i&&c) to ...a.map(x=>i<2?x:x%i&&c), that's no shorter. If you mean move it into the other .map, perhaps... \$\endgroup\$ – ETHproductions Feb 10 '17 at 15:03
2
\$\begingroup\$

Python 2 - 197 bytes

Switched to Python 2 for easier input handling and allowing `` for string conversion. Uses gmpy2 for generating the next prime. Output format still based on previous Python 3 submission (see below), namely filling a list g with symbols and formatting it.

import gmpy2
i=input()
n=len(i)+1
p=1;g=[' ']+i
while p<i[-1]:
 p=gmpy2.next_prime(p)
 t=['*'[m%p:]for m in i]
 if'*' in t:g+=[p]+t
print((('{:>%d}'%(len(`i[-1]`)+1)*n+'\n')*(len(g)/n)).format(*g))

Try it online!

Explanation

For those who don't want to decode it themselves.

import gmpy2                    # arithmetic library
i=input()
n=len(i)+1                      # saves bytes by not needing ()
                                # afterwards
p=1                             # starting number
g=[' ']+i                       # initialsing header row
while p<i[-1]:                  # looping until last character
  p=gmpy2.next_prime(p)         # get the next prime
  t=['*'[m%p:] for m in i]      # verify whether p is a 
                                # divisor of each number
  if'*'in t:g+=[p]+t            # if any divisor found, append
                                # p + divisors to g.
print(
    (('{:>%d}'%(len(`i[-1]`)+1) # compute right formatting element
                                # for length of last character + 1
        *n+'\n'                 # repeat for each input + once
                                # for the prime and add newline
     )*(len(g)/n)               # repeat row format until g
                                # can be inserted
    ).format(*g)                # format using g
)


Previous

Python 3 - 251 bytes

Pretty sure someone can do better. Based on this answer for generating the primes < k.

i=list(map(int,input().split(',')))
l=len(str(i[-1]))+1
n=len(i)+1
g=[0]+i+sum([l for l in [[k]+[j%k==0for j in i]for k in range(2,i[-1])if all(k%f for f in range(2,k))]if 1in l],[])
print((('{:>%d}'%l*n+'\n')*(len(g)//n)).format(*g).replace('0',' '))

Ungolfed version and explanation will follow.

\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – AdmBorkBork Feb 9 '17 at 14:06
  • 1
    \$\begingroup\$ Instead of i=list(map(int,input().split(','))), you could just do i=input(), and take input in the form [1, 2, 3, 4]. \$\endgroup\$ – nedla2004 Feb 9 '17 at 20:50
  • \$\begingroup\$ Thanks, I didn't know that. But I'm going to rework it later anyway :). \$\endgroup\$ – PidgeyUsedGust Feb 9 '17 at 20:56
  • \$\begingroup\$ You can save 2 bytes with p=gmpy2.next_prime(p);t=['*'[m%p:]for m in i], and removing the space in if"*" in. \$\endgroup\$ – Trelzevir Feb 13 '17 at 18:19
1
\$\begingroup\$

Mathematica, 165 bytes

Rather verbose - maybe someone can do something with it:

(j=Join;a=#[[All,1]]&/@FactorInteger@#;b=Sort@DeleteDuplicates@Flatten@a;Grid[j[{j[{""},#]},Transpose@j[{b},Table[If[MemberQ[a[[t]],#],"*",""]&/@b,{t,Length@a}]]]])&
\$\endgroup\$
1
\$\begingroup\$

Bash + GNU utilities, 134 133 132 125 123 bytes

q=printf\ ;u=$q%9s
$u
$q%9d $@
echo
for p in $($u\\n `factor $@`|bc|sort -un)
{
$q%9d $p
for x;{ ((x%p))&&$u||$u X;}
echo
}

Try it online!

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

Python 2, 181 179 bytes

-2 bytes thanks to FlipTack

n=input()
p=[]
t="%%%ss "%len(`n[-1]`)*-~len(n)
print t%(('',)+n)
i=2
while n[-1]/i:
 if all(i%j for j in p):
	p+=[i];s=['*'[m%i:]for m in n]
	if'*'in s:print t%tuple([i]+s)
 i+=1

The input must be a tuple.
Try it online!

\$\endgroup\$
  • \$\begingroup\$ Does all(i%j for j in p) work instead of using map? \$\endgroup\$ – FlipTack Feb 9 '17 at 22:07
  • \$\begingroup\$ @FlipTack yes, It was better, but I changed some thing and forgot the update this \$\endgroup\$ – Rod Feb 9 '17 at 22:28
1
\$\begingroup\$

Batch, 451 bytes

@echo off
set/am=0,w=2,p=1
for %%n in (%*)do set/a"n=m-%%n,m+=(n>>31)*n
for /l %%i in (0,1,9)do set/am/=10,w+=!!m
set s=
for %%n in ("" %*)do set t=%%~n&call:t
set v=%*
:g
if not %s: =%==%p% echo%s%
if %m%==1 exit/b
set/at=p+=1,m=0
set s=
call:t
set v=&for %%n in (%v%)do set n=%%n&set t=&call:c
goto g
:c
set/ar=n%%p
if %r%==0 set/an/=p&set t=*&goto c
set/a"m|=n
set v=%v% %n%
:t
set t=           %t%
call set s=%%s%%%%t:~-%w%%%

Explanation: Starts by calculating the field width w via the maximum of the input values m. Generates the first line of output by padding an empty string and the input numbers to the width w using the subroutine t. Then loops through the integers starting at 2, generating the line of output by padding the integer and then calling the subroutine c to pad an empty string or an asterisk as appropriate for each value, however the generated line is then skipped if it contains no asterisks. As the output is generated, each value is divided by the integer until it would leave a remainder, so the loop terminates when no value is greater than 1.

Note that the set v= gets executed after the %v% is substituted into the for loop on the same line.

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

Python 2, 157 148 146 145 143 bytes

def p(*t):print'%%%ds '%len(`x[-1]`)*len(t)%t
def f(x):k=m=1;p(' ',*x);exec"r=[n%k and' 'for n in x]\nif 0in m%k*r:p(k,*r)\nm*=k*k;k+=1;"*x[-1]

Uses 0 instead of *, as allowed by the rules.

Try it online!

Background

To identify primes, we use a corollary of Wilson's theorem:

corollary of Wilson's theorem

How it works

The first line defines a helper function.

def p(*t):print'%%%ds '%len(`x[-1]`)*len(t)%t

p takes a variable number of arguments which it stores in the tuple t.

The '%%%ds '%len(`x[-1]`) uses a format string to construct a format string; %% is a literal percent sign, %d is a placeholder for the integer that len(`x[-1]`) returns, i.e., the number of digits of the last element in x (the input, not yet defined), and is literal.

If, e.g., the last element of x has three digits, this yields %3s , which *len(t) repeats once for every element of x. Finally, %t applies that format string to the tuple t, constructing a string of t's elements, space-separated and all right-justified to a certain length.

The second line defines the actual submission: a function f that takes a list x as input. After replacing the exec statement, which executes the string it precedes x[-1] times, with a for loop, we get the following code.

def f(x):
    k=m=1;p(' ',*x)
    for _ in range(x[-1]):
        r=[n%k and' 'for n in x]
        if 0in m%k*r:p(k,*r)
        m*=k*k;k+=1

First, f initializes k and m to 1. Note that (k - 1)! = 0! = 1 = m.

Then, p(' ',*x) prints a space and the integers in x, using the function p.

Now, we enter the loop to print the remaining output.

First, r=[n%k and' 'for n in x] constructs the list of the remainders of each integer n in x divided by k. Positive remainders, i.e, remainders that do not correspond to multiples of k, are truthy and get replaced with a space by and' '.

Next, we construct m%k*r. Since m = (k - 1)!, by the corollary of Wilson's theorem, this will be simply r if k is prime, but an empty list if not. If there is at least one 0 in the result, i.e., if k is prime and at least one integer in x is divisible by k, 0in m%k*r will return True and p(k,*r) get called, printing k and the divisibility indicators: 0 if divisible, a space if not.

Finally, we multiply m by and increment k, so the quality m = (k - 1)! continues to hold.

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

MATL, 31 bytes

pYfu!Gy\~h0GhwvVZ{'(?<!\d)0'0YX

This uses 1 instead of *, as allowed by the challenge.

Try it online! Or verify all test cases.

Explanation (outdated)

p           % Implictly input array of numbers. Push product of array
Yf          % Prime factors as a row vector
u           % Keep only unique values
!           % Transpose into column vector
G           % Push input again
y           % Duplicate column vector of unique prime factors onto top
\           % Modulo, element-wise with broadcast
~           % Negate
h           % Concatenate horizontally
0           % Push 0
G           % Push input again
h           % Concatenate horizontally
w           % Swap
v           % Concatenate vertically
V           % Char array representation
Z{          % Convert to cell array of strings. Each row gives a string
'(?<!\d)0'  % Push this string: match '0' not preceded by a digit
0           % Push this string: '0' will be replaced by char 0
YX          % Regexp replace
            % Implicit inoput. Char 0 is displayed as space
\$\endgroup\$
0
\$\begingroup\$

Racket 176 bytes

(let((p printf))(display"   ")(for((x nl))(p" ~a " x))(displayln"")(for((i '(2 3 7 11)))
(p"~a  " i)(for((j nl))(if(member i(prime-divisors j))(p" * ")(p"   ")))(displayln"")))

Ungolfed:

(define (f nl)
  (let ((p printf))

    (display "   ")
    (for ((x nl))
      (p " ~a " x))
    (displayln "")

    (for ((i '(2 3 7 11)))
      (p "~a  " i)
      (for ((j nl))
        (if (member i (prime-divisors j))
            (p " * ")
            (p "   ")))
      (displayln ""))))

Testing:

(f '(6 9 14 22))

Output:

    6  9  14  22 
2   *     *  * 
3   *  *       
7         *    
11            * 
\$\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.